[BaekJoon-17087] 숨바꼭질 6

문제

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

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

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

입력

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

출력

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

예제 입력 1

3 3
1 7 11

예제 출력 1

2

예제 입력 2

3 81
33 105 57

예제 출력 2

24

예제 입력 3

1 1
1000000000

예제 출력 3

999999999

해결

한 번 걸을 때마다 위치는 D만큼 변한다. 따라서 출발점 S에서 동생 위치 Ai에 닿으려면 |Ai-S|가 D의 배수여야 한다. 방향을 바꿀 수 있어도 이동 거리의 합은 D의 정수배라는 조건은 변하지 않는다. 모든 동생을 찾으려면 모든 거리의 공약수를 골라야 하고, 그중 최대가 최대공약수다. ‘공약수의 합’을 구하는 문제가 아니다.

첫 예제 S=3에서 거리는 |1-3|=2, |7-3|=4, |11-3|=8이다. gcd(2,4,8)=2이므로 답은 2다. 둘째 예제의 거리 48,24,24는 최대공약수가 24다. 동생이 한 명뿐이면 그 거리 자체가 답이라는 점도 같은 식으로 나온다.

코드는 첫 거리를 시작값으로 두고 다음 거리와 유클리드 호제법을 반복한다. gcd(a,b)는 b=0이 될 때의 a이고, 각 거리에서 양쪽 위치를 모두 처리하려고 절댓값을 취한다. 시간 O(N log V), 거리 배열 공간 O(N)이며 V는 최대 위치 차이다. 정렬할 필요는 없다.

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws Exception {
        g2();
    }

    public static void g2() throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String str = in.readLine();
        String[] split = str.split(" ");
        int n = Integer.parseInt(split[0]);
        int s = Integer.parseInt(split[1]);

        String str2 = in.readLine();
        String[] split2 = str2.split(" ");
        int[] a = new int[n];

        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(split2[i]);
            a[i] = Math.abs(x-s);
        }

        int result = a[0];
        for (int i = 1; i < n; i++) {
            result = gcd(result, a[i]);
        }

        out.write(result + "\n");
        out.flush();;
        out.close();
        in.close();
    }

    public static int gcd(int a, int b) {
        while (b != 0) {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
}

문제 사이트 : https://www.acmicpc.net/problem/17087