[JAVA] 백준 (실버2) 17087번 숨바꼭질 6

링크

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

---

문제 설명

(정답률 48.620%)
수빈이는 동생 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 3
1 7 11

---

출력 예제

2

---

정답 코드

1. 수빈이와 동생들 사이의 거리를 구한다.
2. 거리들의 최대공약수가 문제의 답이 된다.

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int n = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken());
        int[] brother = new int[n];
        int[] distance = new int[n];
        int answer = 0;
        st = new StringTokenizer(br.readLine(), " ");
		//동생의 위치 배열
        for (int i = 0; i < n; i++) {
            brother[i] = Integer.parseInt(st.nextToken());
        }
		//동생들과 수빈이의 거리 배열
        for (int i = 0; i < n; i++) {
            distance[i] = Math.abs(s - brother[i]);
        }
		//a, b, c의 최대공약수를 구할 때는
        //GCD( GCD(a, b), c )를 하면 되므로 재귀를 이용하여 반복한다.
        answer = distance[0];
        for (int i = 1; i < n; i++) {
            answer = GCD(answer, distance[i]);
        }

        System.out.println(answer);
    }
	//유클리드 호제법을 통한 최대공약수를 구하는 메소드
    static int GCD(int a, int b) {
        if (b == 0) return a;
        return GCD(b, a % b);
    }
} 

---

정리

처음 풀때는 단순히 동생끼리의 거리와 수빈이와 동생들의 거리 중 최소값을 구하면 되는지 알았는데
3 81
33 105 57
가령 예제가 위와 같이 입력될 때
81-33=47인데 최소값은 24(=81-57)가 되므로 33은 방문할 수 없다.
그러므로 최대공약수를 구해야 모든 위치를 방문할 수 있다.

그리고 최대공약수를 구할 때 유클리드 호제법을 이용하였는데
이는 a와 b의 최대공약수는 b와 a%b의 최대공약수와 같다는 뜻이다.
a%b를 구하다보면 b가 0이 되는 특이점이 존재하는데 이때 최대공약수는 a가 된다.