백준 17087 숨바꼭질 6 문제풀이 ( Java )

17087번: 숨바꼭질 6

import java.io.*;
 
public class Main {
 
    static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // reader writer 생성
 
        String[] info = br.readLine().split(" ");
        // info[0]에 N / info[1]에 S
        String[] temp = br.readLine().split(" ");
 
        int[] distance = new int[temp.length];
 
        for (int i = 0; i < temp.length; i++) {
            if (Integer.parseInt(temp[i]) > Integer.parseInt(info[1])) {
                distance[i] = Integer.parseInt(temp[i]) - Integer.parseInt(info[1]);
            } else {
                distance[i] = Integer.parseInt(info[1]) - Integer.parseInt(temp[i]);
            }
        }
 
        int brothersCnt = Integer.parseInt(info[0]);
 
        int answer = distance[0];
 
        if (brothersCnt != 1) {
            // 동생이 한명이 아니면 최대 공약수를 구한다
            for (int i = 1; i < distance.length; i++) {
                answer = gcd(answer, distance[i]);
            }
        }
 
        bw.write(String.valueOf(answer));
        bw.flush();
 
    }
 
}

이건 솔직히 문제를 좀 모호하게 적어놨다

D가 수빈이가 한번에 움직일 수 걸음의 보폭(?) 이다 

예를 들어 4면 4 , 8 , 12 , 16... 이런 식으로만 움직일 수 있고, 5면 5, 10, 15 ,20 .. 이런 식으로만 움직일 수 있다

이 점만 명확해지면 최대 공약수로 풀 수 있다.

 

여러개의 최대공약수도 결국은 두 수의 최대 공약수를 구하는 것과 같다

예를 들어 a, b , c ,d 가 있다고 치면

a와 b의 최대공약수와 c 사이의 최대 공약수를 구해서 그것과 d의 최대 공약수를 구하면 

a, b, c, d의 최대 공약수가 나온다