BOJ 2981: 검문

문제 링크

입력으로 들어올 수 있는 숫자의 최댓값이 10억임을 확인했지만 혹시나 싶어서 M = 2..min 까지 해봤지만 역시 틀렸었다. 근데 제출 결과가 틀렸습니다가 나온 걸 봐선 그냥 내 풀이 자체가 틀렸을 수도 있겠다.

이 문제는 위와 같은 이유로 다른 방법을 생각해야 하고 그 방법은 GCD를 활용하는 것이다. 입력이 5, 17, 23, 14, 83이면 가능한 M=3인데 입력을 다시 M과 엮어서 표현하면 5=1*3+2, 17=5*3+2, 23=7*3+2, 14=4*3+2, 83=27*3+2이다. 몫 부분을 제외하면 M과 R(나머지)은 공통되게 갖고 있는 것을 확인할 수 있다. 이 문제에서 기억해야 할 트릭은 나머지를 지우는 것이다. 예를 들어 17-5를 계산해보면 (5*3+2)-(1*3+2) = 4*3 - 0 = 4*3이 되어 kM (k는 정수)으로 표현 가능해진다. 이 작업을 입력의 인접한 두 수끼리 해보는 것이다. 그러면 공통되게 kM의 형식을 갖고 있는데 우리가 원하는 것은 M을 찾는 것이니 지금까지 작업을 통해 구해진 수들에 대한 gcd를 구하면 M이 나온다.

이렇게 하면 Step 1.은 끝이다. 추가로 M은 여러 가지가 될 수 있지만 gcd를 통해 구한 값은 이들의 최대치이고 나머지 가능한 M들은 gcd를 통해 구한 M이기 때문에 약수 구하는 방법을 적용하면 문제를 최종적으로 해결할 수 있다. i = 2..sqrt(M)까지 돌면 되는데 만약 M이 제곱수라면 i와 M / i가 같은 상황이 생기므로 set에 저장하면서 추가를 해주면 문제를 해결할 수 있다.

#include <algorithm>
#include <iostream>
#include <set>

using namespace std;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, nums[100];
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
    }

    int m = abs(nums[1] - nums[0]);
    for (int i = 1; i < n; i++)
    {
        m = gcd(m, abs(nums[i] - nums[i - 1]));
    }

    set<int> res;

    for (int i = 2; i * i <= m; i++)
    {
        if (m % i == 0)
        {
            res.insert(i);
            res.insert(m / i);
        }
    }

    res.insert(m);

    for (auto &i : res)
    {
        cout << i << ' ';
    }

    return 0;
}