검문

최소공배수 최소공배수 포스팅에서 다루었던 유클리드 호제법을 사용해 최대공약수를 찾아내는 문제이다.

처음 시도 했던게 3주 전이었는데, 이제야 정답을 제출할 수 있었다. 풀이 방법을 모르면 접근 자체가 힘든 문제인 것 같다.

아래의 그림을 보며 이해해보자.

문제에 주어진 입력 예시에 54를 추가해 ‘6 34 38 54’를 만들었다.

• 특정 숫자 M으로 각각의 수를 나누었을 때 나머지가 모두 같아야 한다.
• 이를 위해서는 위의 그림에 빨간색으로 표시되어 있는 ‘숫자 간 차이’를 M으로 나누었을 때 모두 나머지가 0이어야 한다.
• 예를 들어 M=5라고 가정하면, 6을 5로 나눴을 때 나머지는 1, 34를 5로 나눴을 때 나머지는 4 이렇게 나머지가 달라진다.
• 하지만, 4,16,28의 공통 약수인 2 혹은 4로 각각의 수를 나눈다면, 4, 16, 28을 딱 맞아 떨어지게 이동할 수 있음으로 나머지가 항상 같아지게 된다.

한번에 이동할 수 있는 거리를 M이라고 생각하고, x 좌표를 문제에 주어진 숫자들 이라고 생각하면 이해하기 편할 것이다.

코드로 구현해보자.

위에서 말했듯이 숫자들의 간격을 구하고, 그들의 공통된 약수(1을 제외한)를 모두 찾아 오름차순으로 출력하면 된다. 공통된 약수들을 모두 찾을 수도 있겠지만, 유클리드 호제법을 사용해 최대공약수를 구하고, 그 수의 약수들을 구한다면 시간을 더욱 단축시킬 수 있을 것이다.

CODE

import sys
read=sys.stdin.readline

n=int(input())
num=list(int(read()) for _ in range(n))
#유클리드 호제법을 이용한 GCD
def GCD(x,y):
    while y!=0:
        x,y=y,x%y
    return x

#숫자들 간의 간격을 구한다.
for i in range(n-1):
    num[i]=abs(num[i+1]-num[i])
num.pop()
#숫자들 간의 간격들의 GCD를 구한다.
number=num[0]
for x in num:
    number=GCD(number,x)

answer=set([number])

for i in range(2,1+int(number**(1/2))):
    if number%i==0:
        answer.add(i)
        answer.add(number//i)

answer=list(answer)
answer.sort()
print(*answer)

[다시 풀어보기]