[Baekjoon/백준] 2981번: 검문(C/C++)

단계별로 풀어보기 17단계(정수론 및 조합론) 5번 문제

https://www.acmicpc.net/step/18

정수론 및 조합론 단계

---

백준 2981번: 검문

 

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

2981번: 검문

---

문제 설명

트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다.

상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다.

먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다.

N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.

---

입력과 출력

입력: 첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 같은 수가 두 번 이상 주어지지 않는다. 항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다.

출력: 첫째 줄에 가능한 M을 공백으로 구분하여 모두 출력한다. 이때, M은 증가하는 순서이어야 한다.

---

접근 방법

이번 문제는 종이에 적은 숫자의 개수 N을 입력받아 N개 줄에 걸쳐 적은 숫자를 입력받고, 이 숫자들을 M으로 나눠 나머지가 모두 같게되는 M을 모두 찾아 출력하는 문제다.

처음에는 그냥 쉽게 생각해서 대충 최대 공약수 구해서 계산하면 되겠구나 정도로 쉽게 생각하고 문제 풀이를 진행했는데, 제출 결과 시간 초과가 발생했고 이후 진행이 안되서 결국 인터넷에서 검색하여 이 블로그와 그 외 여러 블로그들을 참고해서 문제를 해결하였다.

일단 중요한 것은 종이에 쓴 N개의 수 모두 M으로 나눈 나머지가 동일해야한다. 그러면 아래 식을 만족하게 된다.

paper[i] = M * arr[i] + r

arr[i] : paper[i]를 M으로 나눴을때의 몫
r : 다른 입력 값들과 같은 나머지 값

하지만 우리는 M을 구하는 것이 목표이므로 이를 정리하면 아래와 같이 나온다.

paper[0] = arr[0] * M + r
paper[1] = arr[1] * M + r
->
paper[1] - paper[0] = (arr[1] - arr[0]) * M
->
paper[i] - paper[i - 1] = M * (arr[i] - arr[i - 1])

여기서 M은 paper[i] - paper[i - 1]의 약수다. 따라서 이 두 수의 공약수가 된다. 이 공약수를 구하는 방법은 paper[i] - paper[i -1]의 최대 공약수를 찾아 그것의 약수들을 구하면 된다. 이렇게 문제를 해결할 수 있다.

뭔가 얼렁뚱땅 끝난 느낌이 크지만 설명이 조금 어려워서 그냥 위 참고 블로그 링크를 보는 것을 더 추천한다..

---

코드

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 101

int paper[MAX], arr[501];

int GCD(int A, int B) {
	int C = A % B;

	while (C != 0) {
		A = B;
		B = C;
		C = A % B;
	}

	return B;
}

int main(int argc, char * argv[]) {
	int N, M, count = 0;
	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> paper[i];
	sort(paper, paper + N);

	M = paper[1] - paper[0];

	for (int i = 2; i < N; i++)
		M = GCD(M, paper[i] - paper[i - 1]);

	for (int i = 1; i * i <= M; i++)
		if (M % i == 0) {
			arr[count++] = i;
			if (i != M / i)
				arr[count++] = M / i;
		}

	sort(arr, arr + count);

	for (int i = 0; i < count; i++)
		if (arr[i] != 1)
			cout << arr[i] << " ";
	cout << endl;

	return 0;
}

---

결과

백준 제출 결과