백준 17087 - 숨바꼭질 6 [파이썬]

https://www.acmicpc.net/problem/17087

17087번: 숨바꼭질 6

 

풀이 과정

동생이 있는곳을 지나치지 않고 방문하려면 움직이는 칸수가 동생과의 거리의 약수여야 한다

=> 모든 동생을 찾기 위한 공통적인 약수의 최대값을 구해야 한다

=> 동생과의 거리의 최대공약수를 구해달라는 말이다

 

GCD(a, b, c) = GCD(GCD(a, b), c)가 성립한다. 3개 이상의 수의 최대공약수를 구할때는 앞에서부터 2개씩 묶어서 구해주면 된다

소스 코드

import sys


def gcd(a, b):
    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()))

for i in range(N):
    A[i] = abs(S - A[i])
answer = A[0]
for i in range(1, N):
    answer = gcd(answer, A[i])

print(answer)