[알고리즘][Python] 백준(BOJ) 17087 숨바꼭질 6_파이썬

 

17087 숨바꼭질 6    www.acmicpc.net/problem/17087

17087번: 숨바꼭질 6

 

 

문제 풀기 전 공부할 것 : 수학, 정수론, 유클리드 호제법

 

 

 

 

 

 

 

풀이

<내용>

• 수빈이가 x+d나 x-d로 모든 동생들을 찾을 수 있어야 한다.
• 수빈이가 모든 동생을 찾기 위해서 수빈이 현재 위치와 동생들의 위치의 차를 구한다.
• (수빈 위치 - 동생 위치)의 절댓값들의 최대공약수가 모든 동생을 찾기 위한 d의 최댓값이다.

 

 

<코드>

def gcd(a, b):
    while b:
        mod = b
        b = a%b
        a = mod
    return a

n, s = map(int, input().split())
a = list(map(int, input().split()))
dif = list(set(abs(a[i]-s) for i in range(n)))
d = min(dif)
for i in range(len(dif)):
    d = gcd(dif[i], d)
    
print(d)