[python] 백준 17087 - 숨바꼭질 6

첫째 줄에 N, S를 받아 온다

(N: 동생의 수, S: 현재 수빈이의 위치)

수빈이의 위치가 X일 때, 1초 후에 X+D나 X-D로 이동할 수 있음

모든 동생을 찾기 위한 D의 최대값

 

→유클리드 호제법 최대공약수(gcd)로 구할 수 있음

1. 현재 수빈이의 위치를 빼줌

2. 위치가 마이너스일 경우 절댓값

3. 각 수의 최대공약수 구하기

import sys
def gcd(a,b):  #유클리드 호제법 gcd
    if b==0:
        return a
    else:
        return gcd(b,a%b)

n,s=map(int,sys.stdin.readline().split())  #동생 수, 수빈이의 현재 위치
a=list(map(int,sys.stdin.readline().split())) #동생들의 위치

li=[]
for i in range(n):  #동생들의 수만큼
    if a[i]-s>=0:  #수빈이 현재 위치와의 차이를 li에 append
        li.append(a[i]-s)
    else:  #0보다 작으면 절댓값
        li.append(abs(a[i]-s))

li2=[]
if n==1:
    print(li[0])  #동생이 한명 뿐이라면 수빈이의 위치와 동생 위치의 차이
else:
    for i in range(n):
        if i+1<len(li):
            li2.append(gcd(li[i],li[i+1]))  #최소공배수 
        else:
            pass
    print(min(li2))  #가장 작은 최소공배수 출력