[백준 2981] 검문

문제출처: https://www.acmicpc.net/problem/2981

풀이

주어진 예제 케이스를 보면, 3개의 수를 정렬 시킨 뒤, 인접한 수의 차를 구한 뒤 그 수들의 최대공약수의 공약수가 정답임을 알 수 있습니다.

이를 검증해 보기 위해 몇가지 테스트 케이스를 만들어서 확인해보았습니다.

1) 8, 14, 17 

 -> 인접한 수의 차 : 6, 3

 -> 최대 공약수: 3

 -> 최대 공약수의 공약수: 3(정답)

2) 8, 12, 22

 -> 인접한 수의 차: 4, 10

 -> 최대 공약수: 2

 -> 최대 공약수의 공약수: 2(정답)

3) 17, 35 ,50 

 -> 인접한 수의 차: 18, 15

 -> 최대 공약수: 3

 -> 최대 공약수의 공약수: 3(정답)

4개, 5개의 숫자의 경우에도 확인해 보았는데 모두 맞았습니다. 따라서 아래의 순서대로 풀이를 진행하면 됩니다. 

1. 입력된 숫자들을 정렬하기

2. 인접한 숫자들끼리의 차를 구한 뒤 그 숫자들의 최대 공약수 구하기 ( 유클리드 호제법 이용)

3. 최대 공약수의 공약수 구하기

주의할 점은 3번 과정 중 반복문의 조건 에서 i의 범위를 주의해야합니다. 수의 최댓값이 10억이므로 계산과정에 따라 시간초과가 날 수 있습니다.

따라서 i의 범위를 줄여서 중복되는 계산 과정을 생략 할 수 있도록 합니다.

코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int arr[100];
int func(int a, int b);
int main()
{
    vector<int>v;
 
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    sort(arr, arr + n);
    int gcd = arr[1] - arr[0];
    for (int i = 2; i < n; i++)
    
         gcd = func(gcd, arr[i] - arr[i - 1]);
    
    //gcd=최대 공약수
    
    //최대 공약수의 공약수 => 답
    for (int i = 1; i * i <= gcd; i++)
    {
        if (i == 1)    
            v.push_back(gcd);
        else
        {
            if (gcd % i == 0) {
                v.push_back(gcd / i);
                //같은 수를 걸러내는 작업
                if((gcd/i)!=i)
                v.push_back(i);
            
            }
        }
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < v.size(); i++)
        cout << v[i] << " ";
    cout << '\n';
    return 0;
}
int func(int a, int b)
{
    int c;
    while (b)
    {
        c = a;
        a = b;
        b = c % a;
    }
    return a;
}