[백준 17087] 숨바꼭질 6 - 자바

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

17087번: 숨바꼭질 6

---

1. 풀이

수빈이와 동생의 거리들의 최대공약수를 구하는 문제.

 

수빈이는 이동을 X+D, X-D로만 가능하고, 하나의 D로 모든 동생을 찾아야 한다.

 

이 문제는 수빈이와 모든 동생들의 거리를 구한 다음, 거리들의 최대 공약수(GCD)를 구하면 된다.

 

N개의 최대공약수는 어렵게 느껴지지만, 사실 첫번째 부터 N개까지 순서대로 최대공약수를 구하면 구해진다.

 

---

2. 코드

import java.util.*;

public class Main {

    public static int GCD(int a, int b){
        if(b == 0)
            return a;
        return GCD(b, a%b);
    }

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

        int N = sc.nextInt();
        int S = sc.nextInt();

        int[] nums = new int[N];
        for(int i = 0; i < N; i++) {
            // int distance = Math.abs(S-sc.nextInt());
            int distance = S - sc.nextInt();
            if(distance < 0)
                distance*=-1;
            nums[i] = distance;
        }

        int result = nums[0];
        for(int i = 1; i < N; i++){
            result = GCD(result, nums[i]);
        }

        System.out.println(result);
        sc.close();
    }
}