[Boj] 백준 C++ #2981 검문

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

2981번: 검문

---

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

int gcd(int a, int b){ //유클리드 호제법을 이용한 최대공약수 구하기 알고리즘
    if(a<b){ //a에 더 큰 수가 놓일 수 있도록 swap
        int tmp = a;
        a = b; b = tmp;
    }
    int r = a % b;
    if(r != 0){
        return gcd(b,r); //gcd(a,b)==gcd(b,r)
    }else{
        return b;
    }
}
void divisor(int a) { // 약수 구하기
	if (a <= 0) {
		return;
	}
	for (int i = 1; i <= a / 2; i++) {
		if (a % i == 0) {
			if(i!=1) cout << i << " "; // 약수를 구하는대로 출력
		}
	}
    cout << a << endl; //마지막으로 자기 자신을 출력
}
int main(){
    int N; cin>>N;
    int arr[N];
    for(int i=0;i<N;i++){
        int tmp; cin>>tmp;
        arr[i]=tmp;
    } // 수를 입력받아 배열에 차례로 저장
    sort(arr,arr+N); //오름차순으로 정렬
    int diff[N-1];
    for(int i=0;i<N;i++){
        diff[i] = arr[i+1]-arr[i]; //이웃한 수의 차를 또다른 배열에 저장
    }
    int ans = diff[0]; //ans의 초기값
    for(int i=0;i<N-2;i++){
        ans = gcd(ans,diff[i+1]);//ans와 diff의 최대공약수를 구하고 이를 ans에 저장함
    }
    divisor(ans); //ans의 약수를 구함
    cout<<endl;
}

---

어떤 수 M으로 나누었을 때, 나머지가 모두 같게 되는 어떤 수 M은? 이걸 생각하는데 좀 시간이 걸렸다.

예제를 보면서 갈피를 잡았다. 백준에서 주어진 예제2를 보면
입력 5 5 17 23 14 83
출력 3 이다.

나머지가 같다는 것은 나눈 수(M)의 배수에 같은 수가 더해진다는 것이다. 
예제 2에서는 출력이 3이니 M이 3임을 아는 상태에서 생각해보자.
5 = 3 * 1 + 2
17 = 3 * 5 + 2
23 = 3 * 7 + 2 
14 = 3 * 4 + 2
83 = 3 * 27 + 2
이처럼 몇 배수인지는 다 다르지만 더해지는 수(나머지)는 2로 같다.
따라서 이를 이용할 수 있다.
17에서 5를 빼면
17 - 5 = (3*5+2) - (3*1+2) = 3*(5-1)
나머지가 상쇄되어 사라지기 때문에 딱 나누어 떨어지게 된다. 
따라서 나머지 없이 M으로 나누어 떨어지는 수, 9가 구해진다.

9 같이 M으로 나누어 떨어지는 수를 여러 개 구해서 그 수들의 최대공약수를 구하면 되겠다고 생각했다.
따라서 입력받은 수를 오름차순으로 정렬해서 그 차이를 diff라는 배열에 저장했다. 그리고 diff 안에 있는 수들에 대해서 최대공약수 연산을 해주었다.

하지만 여기서 하나 더 처리해주어야 할 것이 있었는데, 최대공약수가 아니라 최대공약수의 약수를 출력해야한다는 점이었다. 따라서 약수를 구하는 연산이 필요했다. 단순히 a/2까지 반복문을 돌면서 a가 나누어지는지 다 나누어보는 방식을 이용했다.

 

어려웠다 ..이제 gcd유형도 어렵구나 ... . ... 헉 근데 풀고나니까 골드4였다 어려운거맞네