백준 17087 - 숨바꼭질 6

 

 

-해결방법 

수빈이는 d나 -d로만 움직일 수 있고, 동생들은 자유로운 위치에 있다.

동생이 어떤 위치에 있을 때 D씩 움직여서 잡으려면, 동생은 수빈이와 위치에서 D의 배수만큼 떨어진 자리에 있어야한다.

가령 수빈이가 2에 있고, 동생이 10에 있다면, 수빈이는 2씩 혹은 4씩 움직여야 10에 도달할 수 있다. D가 3이나 5면 수빈이는 절대 10에 갈 수 없을 것이다. 

즉 모든 동생들은 수빈이와의 위치와 차이에서 D의 배수만큼의 위치에 있어야 수빈이가 D씩 움직여서 모두 잡을 수 있다.

 

-1. 수빈이와 동생의 위치의 차이를 구한다.

-2. 위치의 차이들의 최대공약수를 구한다.

 

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] t = br.readLine().split(" ");

        int N = Integer.parseInt(t[0]);
        Long S = Long.parseLong(t[1]);
        String[] narr = br.readLine().split(" ");

        int gcd =0;
        if(N>1) {
            for (int i = 0; i < N - 1; i++) {
               
                int a = (int)Math.abs((Long.parseLong(narr[i])-S));
                int a2 = (int)Math.abs((Long.parseLong(narr[i + 1])-S));
                gcd = i == 0 ? getGCD(a,a2):getGCD(gcd,a2);
                //i가 0일때는 첫번째 수 a,a2 다음부터는 gcd와 다음 수의 최대공약수 

            }
        }else {gcd = (int)Math.abs(S-Integer.parseInt(narr[0]));}
        bw.write(gcd+"");
        bw.flush();
        bw.close();

    }

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

}

 

 

*N개의 최대공약수 gcd(gcd(a,b),c)