백준 2981 검문(C++)

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

2981번: 검문

 

알고리즘 분류: Math, 유클리드 호제법

 

 

 

문제 풀이

먼저 입력 값과 시간을 보면 일일이 다 확인하는 브루트포스로는 풀 수 없다는 것을 알 수 있다. n이 100이고, 최대로 입력되는 값이 10억이므로 브루트포스로는 풀 수 없음을 알 수 있다.

그러면 이 문제는 수학적으로 접근을 해야한다는 것인데, 이 문제를 수식으로 써보면,

먼저 모든 수의 나머지가 같은 경우를 간단히 생각해보면 모든 수가 나누어 떨어지면 된다. 즉, 나머지가 0이 되면 되기에,

x_i % M = x_i - (x_i / M ) * M 이렇게 수식을 만들 수 있다.

그리고 x_i % M = x_i-1 % M이다.

그러므로 x_i - (x_i  / M) * M =  x_i-1 - (x_i-1 / M) * M이 성립된다.

즉, x_i - x_i-1 = ((x_i / M) - (x_i-1 / M)) * M 이다.

 

현재의 인덱스의 값에서 현재의  인덱스 -1의 값을 빼면은 공통된 M을 가지게 되는 것이다.

즉 공통된 M을 가지고 있으면, 두 수는 서로소가 될 수 없다.

 

그러면 최대 공약수가 1이 아닌 수가 존재하게 되는 것이기에 M의 최대 값은 gcd(gcd,arr[i] - arr[i -1])가 되는 것이다.

 

위의 과정을 하기 전에 배열을 한 번 정렬을 하거나, arr[i] - arr[i - 1]의 값을 절대값으로 씌워줘야한다.

이유는 arr[i] - arr[i - 1]의 값이 음수가 될 수 있다. 이 값이 음수가 되면 gcd값 또한 음수가 될 수 있으므로

정렬을 하거나, 절대값을 씌워야한다.

 

이제 최대가 되는 M을 구했다. 여기서 생각해볼 것은 모든 수가 M으로 나누면 같아지는 것이기에 M의 약수로 나누어도

같아진다는 것을 알 수 있다.

 

마지막으로 M의 약수들 까지 출력을 해주면 된다.

여기서 조심해야 할 것이, M의 값이 1억을 넘길 수 있다. 배열의 값들이 최대로는 10억이 들어올 수 있기 때문이다.

그렇기에 2부터 M까지 반복문을 돌면서 약수를 확인하는 방법으로는 시간초가가 날 것이다.

 

그러면 좀더 효율적으로 약수를 찾아야할 것이다.

약수를 구하는데 O(sqrt(n))으로 구할 수 있다.

1부터 n의 제곱근까지만 확인하면 되는데, 1부터 n의 제곱근까지 반복문을 돌면서 약수를 구하고,

그 약수로 n을 나누면 된다.

그러면 10억의 입력이 들어와도 30000번 정도만에 끝날 수 있다.

 

 

전체 코드

1. 정렬로 한 코드

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

int arr[101];
int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	int n; cin >> n;
	vector<int> ans;
	for (int i = 0; i < n; i++) cin >> arr[i];
	sort(arr,arr + n);
	int arr_gcd = arr[1] - arr[0];
	for (int i = 2; i < n; i++) {
		int dis = arr[i] - arr[i - 1];
		arr_gcd = gcd(dis, arr_gcd);
	}
	ans.push_back(arr_gcd);
	for (int i = 2; i <= sqrt(arr_gcd); i++) {
		if (arr_gcd % i == 0) {
			ans.push_back(i);
			if (i != arr_gcd / i) ans.push_back(arr_gcd / i);
		}
	}
	sort(ans.begin(), ans.end());
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << " ";
	}
	return 0;
}

 

2. 절대값으로 한 코드

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

int arr[101];
int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	int n; cin >> n;
	vector<int> ans;
	for (int i = 0; i < n; i++) cin >> arr[i];
	int arr_gcd = abs(arr[1] - arr[0]);
	for (int i = 2; i < n; i++) {
		int dis = abs(arr[i] - arr[i - 1]);
		arr_gcd = gcd(dis, arr_gcd);
	}
	ans.push_back(arr_gcd);
	for (int i = 2; i <= sqrt(arr_gcd); i++) {
		if (arr_gcd % i == 0) {
			ans.push_back(i);
			if (i != arr_gcd / i) ans.push_back(arr_gcd / i);
		}
	}
	sort(ans.begin(), ans.end());
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << " ";
	}
	return 0;
}