[BOJ] 2981 검문

문제 링크

 

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

 

모든 알고리즘 문제는 C++로 구현되어 있습니다.

 

이 문제는 주어진 수들 간의 차를 전부 구한 뒤, 그 값들의 최대 공약수의 약수를 구해주면 풀 수 있다. 이런 방식으로 답을 구할 수 있는 이유를 알아보자.

 

주어진 수들을 크기 순으로 나열했을 때, 각각의 수들을 x0, x1, x2, ... ,xn이라 하자. 각각의 수들은 임의의 수 m으로 나눴을 때 모두 동일한 나머지 k를 가지므로 다음과 같이 표현할 수 있다.

 

 

x0=a0*m+k

x1=a1*m+k

x2=a2*m+k

.

.

.

xn=an*m+k

(a0, a1, ... , an : x0부터 xn을 m으로 나눴을 때의 몫)

 

xn과 x0의 차는 (an-a0) * m으로 나타낼 수 있다. 이때 m은 xn-x0의 약수가 된다. 다른 값들 사이의 차도 비슷하게 나타낼 수 있으며, 이 값들의 공약수 집합을 찾아내면 그 값이 m이 된다. 따라서 주어진 수들 간의 차를 전부 구하고, 그 값들의 최대 공약수의 약수를 구해주면 가능한 m을 전부 찾을 수 있다.

 

전체 코드는 다음과 같다.

 

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
//2981 검문
int getGcd(vector<int> sub) {  //최대공약수를 구하는 함수
	int i, j, ret=1;
	for (i = 2; i <= sub[0]; ) {
		int chk = 0;
		for (j = 0; j < sub.size(); j++) {
			if (sub[j] % i != 0) {
				chk = 1;
				i++;
				break;
			}
		}
		if (!chk) {
			for (j = 0; j < sub.size(); j++) sub[j] /= i;
			ret *= i;	
		}
	}

	return ret;
}

int main() {
	int i, j, n, gcd;
	int arr[100];
	vector<int> sub, yak;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

	sort(arr, arr + n);
	for (i = 0; i < n; i++) {
		for (j = i + 1; j < n; j++) {
			sub.push_back(arr[j] - arr[i]);
		}
	}
	sort(sub.begin(), sub.end());
	gcd=getGcd(sub);
	for (i = 2; i*i <= gcd; i++) {
		if (gcd % i == 0) {
			yak.push_back(i);
			yak.push_back(gcd / i);
		}
	}
	yak.push_back(gcd);
	yak.erase(unique(yak.begin(), yak.end()), yak.end()); //중복값 제거
	sort(yak.begin(), yak.end());
	for (auto it = yak.begin(); it != yak.end(); it++) {
		printf("%d ", *it);
	}
}