문제
수빈이는 동생 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값의 최댓값을 출력한다.
풀이 및 회고
풀이
현재 수빈이의 위치와 각 동생들의 위치 사이의 모든 거리에 대한 최대공약수가 해당 문제의 정답이다. 정해진 D만큼 움직이면서 모든 동생들의 위치에 도달할 수 있어야하기 때문이다.
회고
GCD를 사용해야하는 건 알았지만 처음에 풀이를 잘못생각하는 바람에 3번이나 틀려버렸다. 처음에 생각한 방식은 단순히 수빈이와 가장 가까운 두 동생의 위치만 고려하는 방식이었는데 도대체 왜 그렇게 생각한지는 모르겠다. 결국은 반례 찾으러 질문 게시판 갔다가 깨달았다. 재활치료 쉽지 않네.. 틀린 코드들도 전부 커밋해두어야겠다..
코드
def gcd(x: int, y: int) -> int:
return gcd(y, x % y) if y else x
n, s = map(int, input().split())
position_list = list(map(int, input().split()))
result = abs(s - position_list[0])
for i in range(1, len(position_list)):
tmp = abs(s - position_list[i])
result = gcd(result, tmp)
print(result)
