[알고리즘/문제풀이/BOJ 2981번] 검문

검문 문제는 최대공약수를 활용하는 문제이다.

두 수를 어떤 수로 나누었을 때 나머지를 같게 하는 수는 두 수의 차의 모든 약수이다. 또한 두 수의 차의 모든 약수는 두수를 나머지가 같게 나눈다.

위의 명제는 귀류법과 a=bq+r의 식을 활용하여 증명할 수 있다.

위의 두 문장은 두 수를 나누었을 때 나머지를 같게 만드는 어떤 수가 두 수의 차의 약수와 동일하다는 것을 알려준다.

M개의 수를 나머지가 같게 만드는 어떤 수를 찾아야하므로 M개의 수를 정렬하고 순차적으로 두 수의 차의 최대공약수를 계산하여야 한다. 최종적으로 M개의 수를 나누었을 때 같은 나머지를 같게 하는 어떤 수들을 약수로 같는 최대공약수가 얻어진다. 이 최대공약수의 모든 약수를 출력함으로써 문제는 해결된다.

주의할 점은 마지막에 구한 최대공약수의 약수를 출력할 때 최대공약수의 제곱근을 고려하는 것처럼 for문 반복횟수를 최대한 줄이려고 노력해야한다는 점이다. 입력값의 크기가 10억이 되며 이는 최대공약수의 크기가 10억이 될 수 있다는 것을 암시하기 때문이다. 1부터 10억까지 반복하는 것은 비효율적일 뿐만 아니라 시간초과의 원인이 된다.

작성한 코드는 다음과 같다.

---

#include<stdio.h>

int N;
int num[120];
int temp;
int gcd_;
int factor[50000];
int k = 0;

int gcd(int a, int b) {
	int temp;
	
	if (a < b) {
		temp = a;
		a = b;
		b = temp;
	}

	while (a % b != 0) {
		temp = b;
		b = a % b;
		a = temp;
	}

	return b;
}

int main(void) {
	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf("%d", &num[i]);
	}

	for (int i = 0; i < N-1; i++) {
		for (int j = 0; j < N - 1 - i; j++) {
			if (num[j] > num[j + 1])
			{
				temp = num[j];
				num[j] = num[j + 1];
				num[j + 1] = temp;
			}
		}
	}
	
	gcd_ = num[1] - num[0];
	for (int i = 0; i < N-1; i++) {
			gcd_ = gcd(gcd_, num[i+1] - num[i]);
	}

	for (int i = 1; i*i <=gcd_; i++) {
		if (i * i == gcd_) {
			printf("%d ", i);
		}
		else {
			if (gcd_ % i == 0) {
				factor[k++] = gcd_ / i;
				if(i!=1)
					printf("%d ", i);
			}
		}
	}
	
	for (int i = k-1; i >=0; i--) {
		printf("%d ", factor[i]);
	}
}

문제의 지문은 다음의 링크에서 확인할 수 있다.

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