백준 17087 숨바꼭질 6 (Java)

URL

https://www.acmicpc.net/problem/17087

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값의 최댓값을 출력한다.

생각

• 수빈이의 위치가 3이고 동생들의 위치가 각각 [1, 7, 11]이라 할 때, 3+D or 3-D 만큼 이동했을 때 1, 7, 11의 위치로 수빈이가 갈 수 있어야 합니다.

• 수빈이와 동생들 간의 거리를 각각 구하고 각 거리의 최대공약수를 구하면 D가 될 것입니다.

• 각 거리의 값이 [a, b , c ,d] 가 있다고 가정하고, a와 b의 최대공약수와 c의 최대 공약수를 구하고, 그것과 d의 최대 공약수를 구하면
  a, b, c, d의 최대 공약수가를 구할 수 있습니다.

성공 코드

import java.util.Scanner;

public class Main {
    public static int gcd(int a, int b) {
        if(b == 0) {
            return a;
        } else {
            return gcd(b, a%b);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int brotherCount = scanner.nextInt();
        int position = scanner.nextInt();
        int[] brotherPositionArr = new int[brotherCount];

        for (int i=0; i<brotherCount; i++) {
            int brotherPosition = scanner.nextInt();

            brotherPositionArr[i] = (position > brotherPosition) ? position - brotherPosition : brotherPosition - position;
        }

        int gcd = brotherPositionArr[0];

        if(brotherCount > 1) {
            for(int i=1; i<brotherCount; i++) {
                gcd = gcd(gcd, brotherPositionArr[i]);
            }
        }

        System.out.println(gcd);
    }
}