[BOJ/Silver 2] 백준 17087 숨바꼭질 6(C++)

문제 링크

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

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값의 최댓값을 출력한다.

예제 입력 1

3 3
1 7 11

예제 출력 1

2

예제 입력 2

3 81
33 105 57

예제 출력 2

24

예제 입력 3

1 1
1000000000

예제 출력 3

999999999

알고리즘 분류

• 수학

풀이

수빈이는 무조건 D만큼의 거리만 이동할 수 있고, 모든 동생들을 찾아야 한다.

따라서, 수빈이와 동생들 사이의 거리의 최대공약수만큼 이동해야 모든 동생들을 찾을 수 있다.

몇 초 안에 찾으라는 말은 하지 않았기 때문에 시간은 생각할 필요는 없다.

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100001
#define LL long long

using namespace std;
LL N, S, D;
LL A[MAX];
vector<LL> Vec;

LL GCD(LL N, LL M) {
	while (1) {
		LL R = N % M;
		if (R == 0) {
			return M;
		}
		N = M;
		M = R;
	};
}

void Input() {
	cin >> N >> S;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		Vec.push_back(abs(A[i] - S));
	}
}

void Settings() {
	if (Vec.size() == 1) {
		D = Vec[0];
	}
	else {
		sort(Vec.begin(), Vec.end());
		Vec.erase(unique(Vec.begin(), Vec.end()), Vec.end());
		D = GCD(Vec[1], Vec[0]);
		for (int i = 2; i < Vec.size(); i++) {
			D = GCD(Vec[i], D);
		}
	}
}

void Find_Answer() {
	cout << D << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}