백준 js 17087: 숨바꼭질 6

문제

수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다.

수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다.

모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 105)과 S(1 ≤ S ≤ 109)가 주어진다. 둘째 줄에 동생의 위치 Ai(1 ≤ Ai ≤ 109)가 주어진다. 동생의 위치는 모두 다르며, 수빈이의 위치와 같지 않다.

출력

가능한 D값의 최댓값을 출력한다.

예제 입력 1

3 3

1 7 11

예제 출력 1

2

예제 입력 2

3 81

33 105 57

예제 출력 2

24

예제 입력 3

1 1

1000000000

예제 출력 3

999999999

 

풀이

문제는 S를 기준으로 D의 배수 만큼씩 이동하는 조건으로 각 위치에 있는 동생들을 찾는 것이다.

 

수빈이는 D만큼씩 이동이 가능한 것이고 1초에 D, 2초에 2*D만큼씩 이동해서 동생을 모두 찾을 수 있는 D를 

구하는 것이다.

 

그렇기 때문에 D는 수빈이 위치에서 각 동생들 위치까지의 거리 중 공통된 약수를 구하면 된다.

즉, 각 거리의 최대공약수를 구하는 문제이다.

 

예를 예제 1로 들어보면

3 3

1 7 11

 

수빈은 3에 위치해있고, 각 동생들을 1, 7, 11에 위치해 있다. 이 세 동생을 모두 찾을 수 있는 각 거리의 최대공약수를 구하면된다.

|1 - 3| = 2

|7 - 3| = 4

|11 - 3| = 8

각 동생들의 위치서부터 수빈이 위치까지의 거리는 2, 4, 8이다.

이 수들의 최대 공약수는 2이다.

수빈이는 2씩 움직여서 모든 동생을 찾을 수 있다.

 

최대공약수를 구해야 하는 수가 n개 있다면

(GCD(GCD(1, 2),3)4)..) 이런식으로 하나씩 최대공약수를 구한 후 이 최대공약수와 다음 수의 최대공약수를 구해주면 된다.

---

우선 2번째 줄에 있는 각 값들을 수빈이 위치를 나타내는 input[0][1]을 기준으로 절댓값을 구해준다.

/*input = [ [ '3', '3' ], [ '1', '7', '11' ] ]*/
const base = parseInt(input[0][1]) // 수빈 위치
const [...eachDistance] = input[1].map(x => Math.abs(+x - base)); 
// 각 동생들과 수빈이의 거리 배열

최대공약수를 구하는 걸 유클리드 호제법을 이용

const getGCD = (a, b) => {
	let r;
    while(b) {
    	r = a % b;
        a = b;
        b = r;
    }
    return a;
}

그리고 eachDistance에 있는 수들의 최대공약수를 구한다.

for(let i = 2; i < eachDistance.length; i++) {
	tmp = getGCD(tmp, eachDistance[i]);
}

 

전체코드