[백준/Python3] 17087 숨바꼭질 6

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

---

풀이

수빈이의 위치 S가 주어지고, 나머지 동생 들의 위치가 주어졌을 때 X-D or X+D로 모든 동생을 찾을 수 있는 D의 최댓값을 구하는 문제다. 동생들을 찾을 동안 D의 값은 바꿀 수 없다.

이 문제는 최대 공약수를 이용해 해결할 수 있다. 모든 동생들과 수빈이 사이의 거리를 각각 구한 뒤 그 거리의 최대 공약수가 D의 값이 된다.

코드

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

N, S = map(int, input().split())
brothers = list(map(int, input().split()))
ans = 0

if N == 1:
    ans = abs(brothers[0] - S)
else:
    temp = abs(brothers.pop() - S)
    while brothers:
        brother = brothers.pop()
        distance = abs(S - brother)
        if temp >= brother:
            temp = gcd(temp, distance)
        else:
            temp = gcd(distance, temp)
    ans = temp
print(ans)