[C++] 백준 2981번 : 검문

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

2981번: 검문

---

 문제 풀이

수학적인 사고를 요구하는 문제이다!!

문제에서 찾아야 하는 M은 같은 나머지(이하 R)를 만드는 숫자이다.

어떤 값 arr[i]를 M으로 나눴을 때 나머지가 R이 나오면 식은 다음과 같을 것이다.

  arr[i] = M × (arr[i] / M) + R

그렇다면 다음 값들은 arr[i+1] = M × (arr[i+1] / M) + R 이런식으로 이어진다.

여기서 R을 없애주기만 한다면 M을 구하기가 더 쉬워질 것이다. 그러기 위해서 다음식을 빼줄 것이다.

빼주면 식은 arr[i] - arr[i+1] = M × (arr[i] / M - arr[i+1] / M)이 나온다.

식을 보기 쉽게 조금 바꿔주면 A[i] = M × B[i] 이다! 다음식들은 A[i+1] = M × B[i+1] 와 같이 이어진다.

잘 보면 M이 A배열의 값들의 공약수인 것을 눈치챌 수 있다!

따라서 M의 값이 여러 개인 이유는 공약수들이고 이 공약수들이 최대공약수의 약수들이라는 소리이다!

결국, 이 문제는 arr[i] - arr[i+1] 들의 최대공약수의 약수들을 구하는 문제이다!

 

 변수

Set ans : 정답을 저장하는 셋 // 중복 값을 제거해야 하는데 편리한 셋이 있어서 사용함

 

 함수 GCD

최대공약수를 구하는 함수, 유클리드 알고리즘으로 구현!

 

 함수 Solution

최대공약수를 편하게 구하기 위해서 정렬부터 한다.

이후 입력받은 값들의 최대공약수를 구하기 위해서 반복문을 쓴다.

우리가 원하는 정답은 최대공약수의 약수들이므로 반복문을 통해서 약수들을 셋 ans에 저장한다.

i * i <= gcd는 시간을 줄이기 위해서 사용했다. 반까지만 따지면 이후 값은 굳이 따질 필요가 없기 때문이다. 

가장 큰 공약수인 gcd를 마지막에 추가하고 함수를 마무리한다.

 느낀 점

심상치 않은 정답률답게 정말 어렵게 해결한 문제이다. 처음에 arr[i] = M × (arr[i] / M) + R 이 부분을 계속 고민했는데 결국 해결하지 못해서 구글링으로 도움을 조금 받았다. 이후 단번에 이해가 돼서 순식간에 구현하였다. 그래도 아직 갈 길이 먼 것 같다..

 코드

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

int n, gcd;
int arr[101];
set<int>ans;

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

void solution() {
	sort(arr, arr + n);
	gcd = arr[1] - arr[0];
	for (int i = 2; i < n;i++) {
		gcd = GCD(gcd, arr[i] - arr[i - 1]);
	}

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

int main() {
	cin >> n;
	for (int i = 0; i < n;i++) {
		cin >> arr[i];
	}
	solution();
	for (auto ans : ans)
		cout << ans << " ";
}