JAVA 백준 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)가 주어진다. 동생의 위치는 모두 다르며, 수빈이의 위치와 같지 않다.

3 3
1 7 11
3 81
33 105 57
1 1
1000000000

출력

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

2

24

999999999

알고리즘 분류

유클리드 호제법(euclidean), 수학(math), 정수론(number_theory)

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(token.nextToken());
        int S = Integer.parseInt(token.nextToken());

        token = new StringTokenizer(br.readLine(), " ");
        Integer[] pivot = new Integer[N];
        for (int i = 0; i < N; i++) {
            int A = Integer.parseInt(token.nextToken());    // 동생의 거리
            pivot[i] = Math.abs(S - A);    // 나와 동생의 거리차
        }
        Arrays.sort(pivot, Collections.reverseOrder()); // 유클리드호제법은 역정렬이 가정되어야 한다
        int gcd = pivot[0];
        for (int i = 0; i < N; i++) {
            gcd = Euclidean(gcd, pivot[i]);    // 최대 공약수
        }
        System.out.println(gcd);
    }

    static int Euclidean(int a, int b) {
        if (b == 0) return a;
        return Euclidean(b, a % b);
    }
}