백준 2981번 검문 _ 최대공약수 (c++)

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

2981번: 검문

백준 2981번 검문

이 문제.. 시작부터 정답률과 정답자 수를 보니 심상치 않았다..

2981번 검문 문제의 핵심은 이 문제를 수학적으로 어떻게 풀 지 정의를 내릴 수 있느냐이다.
브루트포스로 푼다면 모든 가능한 수를 탐색해 볼 수 있겠지만, 낮은 정답률은 우리에게 그렇게 풀면 시간 초과 날걸? 이라는 것을 말해주고 있다.

그렇다면 이 문제는 어떻게 접근할 수 있을까?

어떤 수 A, B, C가 있고 이들을 K로 나눈 나머지가 항상 D야! 라는 말은 무슨 말일지 생각해보자..
(A-D), (B-D), (C-D)를 K로 나눈 나머지는 항상 0이야! 라는 말이 된다.
이게 이 문제의 핵심이다! 그렇다면 K가 될 수 있는 수는 (A-D), (B-D), (C-D)의 공약수가 된다는 것이다.
그리고 이 공약수는, 최대공약수의 약수가 될 것이다.
그러면 여기서 어떤 두 수 A와 B의 최대공약수는 어떻게 구할 수 있을까?
그것을 이해하기 위해서는 A, B(A>B)의 최대공약수는 만약 A가 B로 나누어 떨어지지 않는다면, A-B와 B의 최대공약수와 같다는 것을 이해할 수 있어야 한다.
이유는 A가 최대공약수 c의 a배이고 B가 최대공약수 c의 b배라고 생각해보면 훨씬 쉽게 이해할 수 있다.
A와 B가 a*c와 b*c 라면, 우리는 c를 찾기 위해서 계속 계수를 줄여나갈 것이고,
(a-b)*c와 b*c도 마찬가지로 c의 배수이니 A-B와 B의 최대공약수는 여전히 유지되고 있다.
따라서 계수를 줄여나가며 최종적으로 c가 출력되도록 하는 재귀함수를 하나 만들어주어야할 것이다.

그럼 여기서 그치지 말고 한 스텝 더 나아가서, 이런 생각을 해볼 수 있다.
A,B,C,D,E....Z까지의 수의 최대공약수를 빠르게 구하기 위해서는? (A-B), (B-C)....(Y-Z)의 최대공약수를 구하는 것이다!
이유는 즉, 간격이 좁은 두 수가 있다면 이는 범위를 훨씬 많이 줄여줄 수 있기 때문이다.
결국 이 문제는 주어진 수의 연속된 차이의 최대공약수를 구하는 문제로 바뀌었다!

그 후, 최대공약수의 약수를 출력하면 되지 않을까?
코드를 함께 보자.

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

int N_card;
vector<int> card;
queue<int> answer;

int GCD(int x, int y){ (최대공약수를 구하는 함수)
    if (x%y==0) return y;
    else return GCD(y, x%y);
}

int main(){
    cin >> N_card;
    card.resize(N_card);
    for (int i=0; i<N_card; i++) cin>>card[i];
    sort(card.begin(), card.end()); //카드를 한번 정렬해주자. (연속된 카드의 차를 최소화)

    int gcd = card[1] - card[0];
    for (int i=2; i<N_card; i++) gcd = GCD(gcd, card[i]-card[i-1]); (카드의 차의 최대공약수)

    vector<int> gcd_vector;
    for (int i=1; i<=gcd; i++){ // 최대공약수의 약수 구하기.
        if (gcd%i==0){
            if (i>gcd/i) break; // 모두 다 검사할 필요 없이 중간까지만 구하면 된다.
            gcd_vector.push_back(i);
            if (i==gcd/i) break; // 제곱근이면 하나만 뽑고 멈춰야지.
            gcd_vector.push_back(gcd/i);
        }
    }

    sort(gcd_vector.begin(), gcd_vector.end(), greater<int>());

    while(!gcd_vector.empty()){
        if(gcd_vector.back()!=1) cout << gcd_vector.back() << " ";
        gcd_vector.pop_back();
    }

    return 0;
}

 

끝!