문제

난이도 : 실버2
알고리즘 분류 : 수학, 유클리드 호제법, 정수론

수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다.

수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다.

모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자.

풀이

(거리) = (수빈이의 위치) - (동생의 위치)
동생들과 수빈이의 거리를 구한 뒤에, 이들의 최대공약수를 구하면 된다.
최대공약수를 구할 때는 유클리드 호제법을 이용한다.

동생의 수가 여러 명 이므로, 첫 번째로 나온 최대공약수를 그 다음 번째 최대 공약수를 구할 때 사용한다.

동생이 1명일 경우에는 거리를 그대로 출력함에 주의한다.
동생이 2명일 경우에는 반복할 필요가 없음에 주의한다.

코드

#include <iostream>
using namespace std;

int gcd(int num1, int num2){
    if (num2==0)return num1;
    else return gcd(num2, num1%num2);
}

int main(){
    int N, S; // 동생 N명, 수빈이의 현재 위치 S
    cin >> N >> S;
    int distance[100001]; // 동생과 수빈이의 거리
    for (int i = 0; i < N; i++){
        cin >> distance[i];
        if (S > distance[i])    distance[i] = S - distance[i]; // 양수가 되도록 한다
        else    distance[i] = distance[i] - S;
    }
    if (N == 1) cout << distance[0];
    else if (N == 2)    cout << gcd(distance[0], distance[1]);
    else {
        int result = gcd(distance[0], distance[1]);
        for (int i = 2; i < N; i ++){
            result = gcd(result,distance[i]);
        }
        cout << result;
    }
}