[Python] 백준 / 숨바꼭질 6 / 17087번 / 유클리드 호제법

문제

숨바꼭질 6 문제 링크

수빈이는 동생 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)가 주어진다. 동생의 위치는 모두 다르며, 수빈이의 위치와 같지 않다.

3 3
1 7 11

출력

가능한 D값의 최댓값을 출력한다.

2

접근 방식

코드

def gcd (li : list) -> int: # 여러 수의 최대공약수 반환 함수
    
    n = li[0]
    for i in range(1, len(li)):
        m = li[i]

        n,m = max(n,m), min(n,m)
        while m !=0:
            n,m = m,n%m
        
    return n

import sys

_, s = map(int,sys.stdin.readline().split())
num_li = list(map(int,sys.stdin.readline().split()))

# 수빈이의 위치와 동생 위치 차이값 리스트 
for i in range(len(num_li)):
    num_li[i] = max(s, num_li[i]) - min(s, num_li[i])

print(gcd(num_li))

유클리드 호제법 - 위키백과