[코테] 백준 수학 17087번 문제

17087번 : 숨바꼭질 6

문제 링크

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

문제 설명

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

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

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

입력

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

출력

가능한 D값의 최댓값을 출력한다.

문제풀이

수빈이와 동생들의 거리들의 최대공약수를 구하면 해결되는 문제이다.

import sys
import math
input = sys.stdin.readline

N, S = map(int, input().split())
positions = sorted(list(map(int, input().split())) + [S])
diffArr = [positions[i+1] - positions[i] for i in range(N)]
result = diffArr[0]

for i in range(1, N) :
    result = math.gcd(result, diffArr[i])

print(result)