[108일차] 숨바꼭질 6 - 백준 - 17087(python - 수학, 정수론, 유클리드 호제)

문제 설명

수빈이는 동생 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값의 최댓값을 출력한다.

 

예제 입력, 예제 출력

3 3 1 7 11	2
3 81 33 105 57	24
1 1 1000000000	999999999

 

코드 및 설명

n, s = map(int, input().split(' '))
a_arr = list(map(int, input().split(' ')))
answer = 10**9

for i in range(n):
  answer = min(answer, abs(a_arr[i] - s))
  
print(answer)

 

이 문제를 처음엔 단순하게 주어진 수빈이의 위치에서 동생들의 위치를 뺀 후에 제일 작은 수가 답이겠네라고 생각하고 풀

 

었다. 예제에 있는 답들은 다 맞출 수 있었지만, 채점시 틀렸다고 나왔다. 

3 10 1 6 13

 

만약 위에 코드대로 한다면, 3이 나올테고, 하지만 3으로 되지않는 걸 알 수 있다. 10에서 6으로 갈때 4가 필요한 것 부터 

 

바로 잘못됐다... 초당 같은 거리를 가야하기때문에 위 케이스의 답은 1이 된다.

 

그러므로, 여기서 거리의 차이값의 최대공약수를 구해야한다.

 

밑에 코드처럼 하면 된다.

 

import math

n, s = map(int, input().split(' '))
a_arr = list(map(int, input().split(' ')))
dis = []

for i in range(n):
  dis.append(abs(a_arr[i] - s))
  
answer = dis[0]
for j in range(1, n):
  answer = math.gcd(dis[j], answer)

print(answer)