[백준/2981] 검문 (약수 / 최대공약수)

1. 문제

 

 

 

2. 접근 방법

'어떤 수가 가지고 있는 약수를 빠르게 찾는 알고리즘'

을 모르면 해결이 쉽지 않은 문제이다.

나도 이 알고리즘을 몰랐기 때문에, 처음에는 시간 초과를 겪어 당황스러울 수밖에 없었다.

 

이 문제를 접근하는 방법은 다음과 같다.

---

(1) N개의 숫자를 대상으로, N - 1 만큼 숫자 간의 차이들을 구한다.

(2) 이 N - 1개의 '차이'들 중, 가장 작은 값을 찾는다.

(3) 위에서 구한 가장 작은 값을 대상으로, 1을 제외한 모든 약수를 구한다.

(4) 위에서 구한 모든 약수 중, 전체 숫자를 나눠봤을 때 0으로 나누어 떨어지는 약수들만 출력한다.

---

예시를 들어보자.

다음과 같이 9, 23, 58 의 3개의 숫자가 있다고 가정해보겠다. 

 

그렇다면 위와 같이, 3개의 숫자들의 차이는 14와 35, 2개이다.

 

이 중, 가장 작은 값은 14 이므로, 14의 약수들을 구하면 다음과 같다.

 

이제 이 2, 7, 14 를 대상으로, 모든 '차이' 들에 대해 0으로 나누어 떨어지는 약수만을 출력하면 된다.

 

 

그러므로 최종적으로 '7' 하나만이 정답으로 출력된다.

 

 

 

3. 구현

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

int main(void)
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int arr[100];
	int gap[99];
	vector<int> factors;
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];
	sort(arr, arr + N);
	for (int i = 0; i < N - 1; i++) gap[i] = arr[i + 1] - arr[i];
	sort(gap, gap + N - 1);

	for (int i = 2; i <= sqrt(gap[0]); i++)
	{
		if (gap[0] % i == 0)
		{
			factors.push_back(i);
			if (i != gap[0] / i) factors.push_back(gap[0] / i);
		}
	}
	factors.push_back(gap[0]);
	sort(factors.begin(), factors.end());

	for (auto a = factors.begin(); a != factors.end(); a++)
	{
		int cnt = 0;
		for (int i = 0; i < N - 1; i++)
		{
			if (gap[i] % *a != 0) break;
			cnt++;
		}
		if (cnt == N - 1)
		{
			cout << *a << " ";
		}
	}

	return 0;
}