[백준] 수학 17087번: 숨바꼭질 6

문제

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

Approach

사용 알고리즘: 유클리드 호제법

• 이동할 수 있는 거리는 수빈이의 현재 위치와 동생이 있는 지점과의 거리의 약수가 된다.
• 그러므로 각 거리차들의 gcd를 구하면 된다.

Source Code

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <sstream>
#include <math.h>
using namespace std;


// gcd구하는 함수
int GCD(long long int x, long long int y)
{
    if (y == 0)
        return x;
    return GCD(y, x % y);
}


int main()
{
    int n, s;
    cin >> n >> s;

    // 동생들과의 거리 기록
    vector<int> vec;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        vec.push_back(abs(x - s));
    }
    
    int gcd = vec[0];
    
    // 거리들의 gcd구해서 매번 갱신 
    for (int j = 1; j < n; j++)
    {
        gcd = GCD(gcd, vec[j]);
    
    }
    
    cout << gcd << endl; // 답안 출력
    return 0;
}