[백준][C++] 17087: 숨바꼭질 6

문제

17087번: 숨바꼭질 6

풀이

유클리드 호제법

 

S에서 일정한 간격으로 이동할 때, 모든 A에 도달해야 한다. 즉, 간격이 모든 A와의 차이의 공약수여야만 한다. 이 간격 중 최댓값이므로, 최대공약수가 정답이다.

 

코드

#include <iostream>

using namespace std;

vector<int> diffs;

int gcd(int a, int b)
{
    if (a < b)
    {
        swap(a, b);
    }

    int temp;
    while (b != 0)
    {
        temp = a % b;
        a = b;
        b = temp;
    }

    return a;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, S;
    cin >> N >> S;

    // 현재 위치 S와의 차이를 저장
    for (int i = 0; i < N; ++i)
    {
        int temp;
        cin >> temp;

        diffs.push_back(abs(temp - S));
    }

    // 모든 차이의 gcd를 출력
    int answer = diffs[0];
    for (int i = 1; i < diffs.size(); ++i)
    {
        answer = gcd(answer, diffs[i]);
    }

    cout << answer;

    return 0;
}