백준 17087번 숨바꼭질6 [JAVA]

문제

수빈이는 동생 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값의 최댓값을 출력한다.

 

 

 

알고리즘 설계

 

수빈이의 위치 S에서 동생들이 있는 위치 A1,A2 -- An 까지  S+D 혹은 S-D로 모두 도착하려면  

D값은 [S-A1]과 [S-A2] --- [S-A3]의 약수여야한다

그중에서 D의 최댓값을 구하라고 했으므로  [S-A1]과 [S-A2] --- [S-A3]의 최대공약수를 구하면 되는 문제이다 

 

여기서 POINT는 N개의 수의 최대공약수를 어떻게 구해야지 효율적이냐는 것이다

 

처음에 나는 이중 for문을 사용하여 모든 수를 서로 짝을 이루어 GCD메소드로 넘겨 두 수의 최대공약수를 구하고 그 중에서 가장 작은값이 모든 수의 최대공약수라고 생각하고 구현을 하였다 

이는 답은 맞지만 시간초과를 발생시켰다

 

그 이후에 백준 강의를 보니 이보다 더 효율적으로 N개의 수의 최대공약수를 구하는 방법이 있었다

 

4개의 수 a,b,c,d가 있다면 

1. a,b의 최대공약수를 구하고

2, 1에서 얻은 값과 c의 최대공약수를 구하고

3. 2에서 얻은 값과 d의 최대공약수를 구하면 

4. 3에서 나온 값이 4개의 수의 최대공약수였다

 

 

느낀점: 알고리즘문제를 보고 어떻게 풀까 계속 고민하는것도 좋지만 효율적인 알고리즘 방법을 빨리빨리 습득해서 점점 문제에 효율적으로 접근하는 실력을 기르는것도 중요하다는것을 깨닫았다. 

 

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int s = sc.nextInt();
        int[] brother = new int[n];
        for (int i = 0; i < n; i++) {
            brother[i] = sc.nextInt();
            brother[i] = Math.abs(s - brother[i]);

        }

        int answer=brother[0];
        for (int i = 1; i < brother.length; i++) {
            answer=GCD(answer,brother[i]);

        }
        System.out.print(answer);
    }
    public static int GCD ( int a, int b){
        if (b == 0) {
            return a;
        } else {
            return GCD(b, a % b);
        }
    }
}