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

 

 수빈이의 위치로부터 동생들 사이의 거리를 구한 후, 이들에 대해 최대공약수를 구하면 쉽게 풀리는 문제이다. 최대공약수를 구하는 방법에 대해서는 전에 작성한 글에서 자세하게 다루어 놓았다. 참고하기를 바란다.

 

https://messy-developing-diary.tistory.com/68

GCD 알고리즘

 

 최대 공약수를 구할 수 있는 가, 더 나아가서는 최대 공약수의 의미를 제대로 알고있는 가를 확인하는 문제라 볼 수 있겠다. 코드는 다음과 같다.

 

#include <iostream>
#include <cmath>
#include <vector>

int get_gcd(int a, int b) 
{
	int tmp, n;

	if (a < b) 
	{
		tmp = a;
		a = b;
		b = tmp;
	}

	while (b != 0) 
	{
		n = a % b;
		a = b;
		b = n;
	}

	return a;
}

int main() 
{
	int N, S;
	std::cin >> N >> S;

	std::vector<int> A;

	for (int i = 0; i < N; i++) 
	{
		int data;
		std::cin >> data;

		data = abs(data - S);

		A.push_back(data);
	}

	int gcd = A[0];

	for (int i = 0; i < N; i++) 
	{
		gcd = get_gcd(A[i], gcd);
	}

	std::cout << gcd;

	return 0;
}