백준: 17087 숨바꼭질 6

문제

17087번: 숨바꼭질 6

 

문제 풀이

 최대 공약수를 구할 수 있다면 쉽게 풀 수 있는 문제이다. 나의 위치와 동생들의 위치 차이를 계산한뒤, 전체의 위치에서 최대 공약수를 찾아서 반환하면 문제의 정답이 된다. 최대 공약수를 구할 때 세 수의 최대 공약수를 구한다고 하면 a, b에 대한 최대 공약수를 구하고, 구해진 최대 공약수와 c의 최대 공약수를 구하면 a, b, c의 최대 공약수와 같아진다. 이 성질을 활용하여 코드를 구현하면 간단하게 문제를 풀 수 있다.

 

코드

from sys import stdin


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


if __name__ == "__main__":
    n, s = map(int, stdin.readline().split())
    brothers = list((map(int, stdin.readline().split())))
    dist = []

    for location in brothers:
        dist.append(abs(location - s))

    answer = dist[0]

    if len(dist) > 1:
        for d in dist:
            answer = gcd(answer, d)

    print(answer)