[백준] 17087번 숨바꼭질 6 - Python / 알고리즘 기초 1/2 - 수학 1 (연습)

---

---

---

💡 문제

수빈이는 동생 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만큼씩 움직여 모든 동생과 위치가 같아져야 하므로, 우선 수빈이와 동생들과의 거리의 절댓값을 구해준다.

이후, 동생을 지나쳐서도 안되고 거리가 모자라도 안되기 때문에 모든 동생과 위치가 같아질수 있게 하기 위해선 모든 동생들과의 거리의 최대공약수를 구해주면 된다.

ex) 예제
n = 3, s = 81
arr = [33, 105, 57] -> [48, 24, 24]

gcd(gcd(48, 24), 24) = 24 # gcd(48, 24) = 24

---

📒 코드

from math import gcd

n, s = map(int, input().split())
a = list(map(int, input().split()))
a = [abs(s - num) for num in a]

ans = a[0]
for i in range(1, n):
    ans = gcd(ans, a[i])
print(ans)

---

💭 후기

어떻게하면 한번에 똑같은 거리를 움직여 모든 동생을 찾을 수 있을지 고민하는 문제.

---

🔗 문제 출처

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

---