[백준] 17087번 (python 파이썬)

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

17087번: 숨바꼭질 6

 

import sys

def get_gcd(num1, num2):
  while num2 != 0:
    r = num1 % num2
    num1 = num2
    num2 = r
  return num1

_, S = map(int, input().split())
arr = list(map(int, sys.stdin.readline().split()))
arr = set(map(lambda item: abs(item-S), arr))
d = min(arr)
for i in arr:
  d = get_gcd(i, d)
print(d)

 

이 문제의 핵심은 여러 수들의 최대 공약수를 구하는 것이다.

처음엔 조합(combinations)을 이용해서 두 개의 수를 뽑아 최대 공약수를 구한 다음에 뽑아낸 최대공약수 중 제일 작은 걸 고르는 방법을 생각했다. 시간초과가 나왔다.

 

여러 수들의 최대 공약수를 구할땐 아래와 같은 방법을 이용하자.

1. 여러 수들 중 가장 작은 수와 임의의 수의 최대 공약수를 구한 뒤 저장한다.
2. 구한 최대 공약수와 임의의 수의 최대 공약수를 구해서 덮어쓰기 한다. 
3. 2번을 반복한다.

그럼 자동으로 최대 공약수들 중 제일 작은 최대 공약수가 구해진다.