[C/C++] 백준 2981번 - 검문

 

<코드>

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

int N, gcd;
int x;
vector<int> v, ans;

int GCD(int a, int b) 
{
	if (b == 0) return a;
	return GCD(b, a % b);
}

int main() 
{
	cin >> N;

	// 수들을 입력받고 정렬
	for (int i = 0; i < N; i++) 
	{	
		cin >> x;
		v.push_back(x);
	}
	sort(v.begin(), v.end());

	gcd = v[1] - v[0];
	for (int i = 2; i < N; i++) gcd = GCD(gcd, v[i] - v[i - 1]);

	for (int i = 2; i * i <= gcd; i++) 
		if (gcd % i == 0)
		{
			ans.push_back(i); 
			ans.push_back(gcd / i);
		}

	ans.push_back(gcd);

	sort(ans.begin(), ans.end());
	ans.erase(unique(ans.begin(), ans.end()), ans.end()); // 중복된 원소들 제거

	for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";

}

 

문제의 정답률이 20%밖에 되질 않는 것을 보고 단순하게 생각하면 무조건 시간 초과 에러가 발생하겠구나 생각하였다.
그러나 시간초과코드 외엔 풀이 방법을 도저히 모르겠어서 여러 블로그를 검색해본 결과 풀이 방법은

N-1개의 v[i] - v[i - 1] 값들의 최대공약수 GCD를 구한 뒤,
GCD의 약수들(1을 제외한 약수들)을 출력하는 것이다.

 

 

설명

v[0] = share[0]*M + r
v[1] = share[1]*M + r
...
v[i-1] = share[i-1]*M + r
v[i] = share[i]*M + r

라고 할 때 M을 구하는 것이 목표이다. 문제 조건에 따라 나머지 값인 r은 모두 동일하다. 따라서 위의 식을 아래처럼

v[1] - v[0] = (share[1] - share[0])*M
...
v[i] - v[i-1] = (share[i] - share[i-1])*M

으로 표현이 가능하고 int GCD(int a, int b) 함수를 통해

v[i] - v[i-1] 값들의 최대공약수 GCD = M을 구할 수 있게 된다.

따라서 M으로 가능한 수는 M의 약수(1 제외)들을 출력하면 정답이다.

 

www.acmicpc.net/problem/2981

2981번: 검문