#17087: 숨바꼭질 6

백준 17087번: 숨바꼭질 6

문제:

수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, …, AN에 있다.

수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다.

모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자.

입력:

첫째 줄에 N(1 ≤ N ≤ 105)과 S(1 ≤ S ≤ 109)가 주어진다. 둘째 줄에 동생의 위치 Ai(1 ≤ Ai ≤ 109)가 주어진다. 동생의 위치는 모두 다르며, 수빈이의 위치와 같지 않다.

풀이:

• 이 문제는 처음에 복잡해 보일 수 있지만 최대공약수를 활용하면 쉽게 풀 수 있다. 우선 이 문제를 간단하게 풀이하면 수빈이와 동생의 거리를 구한 뒤 그것의 최대공약수를 구하면 가능한 D의 최댓값을 구할 수 있다.
• 수빈이와 거리를 구할 때 (수빈 위치 - 동생 위치)를 할거면 수빈이보다 큰 수는 마이너스 값이 나오기 때문에 그런 경우에는 앞에 마이너스를 씌운 뒤 저장해주어야 한다.
• 최대공약수는 유클리드 호제법(자세한 설명은 #2609: 최대공약수와 최소공배수을 참고)을 이용하여 구하면 되고 모든 수의 최대공약수는 제일 처음에 두수의 최대공약수를 구한 뒤 최대공약수 값을 나머지 거리 값들과 비교하면서 갱신해주면 된다.

코드:

#include <iostream>

using namespace std;

int main(){
	int num_sib, pos_subin, gcd;
	//입력 
	cin >> num_sib >> pos_subin;
	//동생 위치 저장을 위한 동생 수 크기의 배열 생성 
	int pos_sib[num_sib];
	//배열에 수빈이와의 거리 저장 
	for(int i = 0; i < num_sib; i++){
		int temp;
		cin >> temp;
		//수빈이 위치보다 더 크면 마이너스 씌워주기 
		if(pos_subin > temp) pos_sib[i] = pos_subin - temp;
		else pos_sib[i] = -(pos_subin - temp);
	}
	//유클리드 호제를 위해 gcd 값 초기화 
	gcd = pos_sib[0];
	//배열의 모든 값의 최대 공약수 구하기 
	for(int i = 1; i < num_sib; i++){
		//전에 구한 최대 공약수 값과 계산하여 최대공약수 값 갱신 
		int temp, a = pos_sib[i], b = gcd;
		//큰 수가 a에 오도록 함 
		if(a < b){
			temp = a;
			a = b;
			b = temp;
		}
		//유클리드 호제법 
		while(a%b){
			temp = b;
			b = a%b;
			a = temp;
		}
		gcd = b;
	}
	//출력 
	cout << gcd; 
}