[백준][C++] 2981: 검문

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

2981번: 검문

 

 

 

 

---

- 문제

 

  숫자가 N개 주어졌을 때 무엇으로 이 숫자들을 나누었을 때 나머지가 같을 수 있는지 찾는 문제다.

 

 

---

- 해설

 

  아래에 주석처리 된 부분이 스스로 풀어 본 건데, 마지막 % 조금 남기고 계속 틀리다고 나와서 찾아봤다.

 

예를 들어 3,6,34,38이 주어지면

 

38 - 34 = 4

34 - 6 = 28

6 - 3 = 3

 

이 나오는데, 이 차를 이용해서 유클리드 호제법을 이용해 최소공배수를 구해준다. 

 

결국 나누었을 때 나머지가 같은 것들을 구하는 문제니깐 일정한 등차수열을 이루는 숫자를 구하는 문제라서 이게 통한다.

 

이후에 구한 최소 공배수를 이용해서 약수들을 구하는 방식을 이용해 모든 약수들을 구하고 정렬 후 출력한다.

 

 

---

- 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

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

    int N, temp, tempgcd;
    vector<int> A, M;

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> temp;
        A.push_back(temp);
    }
    sort(A.begin(), A.end());
    tempgcd = A[1] - A[0];
    for (int i = 2; i < N; i++)
    {
        tempgcd = gcd(tempgcd, A[i] - A[i - 1]);
    }
    for (int i = 2; i * i <= tempgcd; i++)
    {
        if (tempgcd % i == 0)
        {
            M.push_back(i);
            if (i != tempgcd / i)
                M.push_back(tempgcd / i);
        }
    }
    M.push_back(tempgcd);
    sort(M.begin(), M.end());

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

    return 0;
}

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

//     int N, temp, percent, tempMeas;
//     vector<int> A, M, meas;
//     cin >> N;
//     for (int i = 0; i < N; i++)
//     {
//         cin >> temp;
//         A.push_back(temp);
//     }
//     sort(A.begin(), A.end());
//     for (int i = 2; i <= A[0]; i++)
//     {
//         percent = -1;
//         for (auto a : A)
//         {
//             if (percent == -1)
//                 percent = a % i;
//             if (percent == a % i)
//             {
//                 continue;
//             }
//             else
//             {
//                 percent = -1;
//                 break;
//             }
//         }
//         if (percent != -1)
//         {
//             M.push_back(i);
//             percent = -1;
//         }
//     }
//     tempMeas = A[1] - A[0];
//     for (int i = 1; i * i < tempMeas; i++)
//     {
//         if (tempMeas % i == 0)
//         {
//             meas.push_back(i);
//             meas.push_back(tempMeas / i);
//         }
//     }
//     for (int i = 1; i < meas.size(); i++)
//     {
//         if (meas[i] > A[0])
//         {
//             percent = -1;
//             for (auto a : A)
//             {
//                 if (percent == -1)
//                     percent = a % meas[i];
//                 if (percent == a % meas[i])
//                 {
//                     continue;
//                 }
//                 else
//                 {
//                     percent = -1;
//                     break;
//                 }
//             }
//             if (percent != -1)
//             {
//                 M.push_back(meas[i]);
//                 percent = -1;
//             }
//         }
//     }
//     sort(M.begin(), M.end());
//     for (auto a : M)
//     {
//         cout << a << ' ';
//     }

//     return 0;
// }

 

---

- 새롭게 알게 된 점

 

X