BOJ 10787번: 숨바꼭질6 [python] 코드와 풀이 - 여러 숫자의 최대공약수

www.acmicpc.net/problem/17087

17087번: 숨바꼭질 6

여러 개의 숫자들 간의 최대공약수를 구하는 문제이다.

100, 360, 25, 10 간의 최대공약수를 구한다고 하면,

gcd(100, 360) = 20

gcd(20, 25) = 5

gcd(5, 10) = 5 

이런 식으로 앞에 두 수의 gcd를 구하고, 결과로 나온 그 gcd값과 다음 수와의 gcd를 구하고, 이런 방식으로 반복하여 여러 수들 간의 gcd를 구한다.

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
n, s = map(int, input().split())
pos = map(int, input().split()) # 동생들의 위치
s_pos = [ abs(p-s) for p in pos] # 동생들과 수빈이의 위치 차이 리스트
ans = 1000000000
if len(s_pos) == 1: # 동생이 한 명일 경우
    print(s_pos[0]) # 둘의 차이를 출력
else:
    for i in range(0, len(s_pos)-1): # 동생 여러 명일 경우
        g = gcd(s_pos[i], s_pos[i+1]) # 위치 차이들 간의 최대공약수
        if ans > g:
            ans = g
    print(ans)