[python] 숨바꼭질 6

백준 17087번

문제 설명

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

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

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

풀이

처음엔 문제가 이해가 잘 안 가서 시간을 좀 날렸다.
찾아야 할 동생 한명당 계산하면 당연히 D의 값은 출발점 S에서 목적지까지의 거리이다.
하지만 여기선 모든 동생을 찾기 위한 D의 최댓값을 구해야 하므로
S부터 A1...AN까지의 거리를 모두 구한 뒤 해당 값들의 최대공약수를 구하면 된다.

예제에 있는대로 찾아야 할 동생이 3명, 수빈이의 위치가 3이고 각각 동생의 위치가 1, 7, 11이라면, 일단 동생 위치에서 수빈의 위치를 뺀 절대값(거리)를 구하면 각각 2, 4, 8이다.
D의 값은 거리의 차이의 약수가 되어야 하므로 2,4,8의 최대공약수를 구하면 정답은 2가 된다.

제출 코드

import sys
from math import gcd

n, s = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
result = 0
distance = []

for i in range(n):
    distance.append(abs(s - int(a[i])))

for i in range(len(distance)):
    result = gcd(distance[i], result)

print(result)