[C++] 백준 17087 : 숨바꼭질 6

 

#include <iostream>
#include <vector>

using namespace std;

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

	return GCD(b, a % b);
}

int main() {
	int N, S;
	cin >> N >> S;
	int minV = 1000000000;
	int input;
	int ans = 0;
	for (int i = 0; i < N; i++) {
		cin >> input;
		int diff = abs(S - input);
		ans = GCD(diff, ans);
	}
	cout << ans;
	return 0;
}

동생들과 수빈이들과의 거리들 중에서

최대 공약수를 구하면 되는 문제이다, 

그러나 동생들이 10000명 까지 있을 수 있고,

위치도 10억까지 있어서, 완전탐색으로는 무조건 시간초과라서 

시간을 줄일 수 있는 방법이 필요했다.

대표적인 수학적 이론이 유클리드 호제법이였다.

GCD 함수에 유클리드 호제법을 통해서 최대 공약수를 갱신해주면

시간복잡도 O(10000*GCD의 재귀호출회수)으로 문제를 해결 할 수 있다.