[BOJ][C++] 백준 17087 숨바꼭질 6
Updated:
17087 숨바꼭질 6
1. 문제 정보
백준 온라인 저지 [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
3 3 1 7 11
예제 입력2
3 81
33 105 57
예제 출력2
24
예제 입력3
1 1 1000000000
예제 출력3
999999999
시간 / 메모리 제한
1초 / 512MB
2. 생각
- 이 문제는 최대공약수 문제였습니다. 수빈이가 서있는 위치와 각 동생들이 서있는 위치의 거리차를 구한 뒤 각 거리차의 약수 중 최대가 되는 수를 구하면 됩니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 A1 S A2 A3 S : 수빈 A1, A2, A3 : 동생
A1 - S = 1 - 3 = 2 A2 - S = 7 - 3 = 4 -> 세 수의 최대 공약수 2 A3 - S = 11 - 3 = 8 - 최대 공약수는 문제 9613번 GCD 합의 내용 중 유클리드 호제법을 이용하여 계산하도록 하겠습니다.
3. 소스코드 (C++)
