[백준] 2981 - 검문 (파이썬)

1. 문제

 

 

2. 코드

import math

n = int(input())
l = []
gcd = 0
m = []

for _ in range(n):
    num = int(input())
    l.append(num)

gcd = abs(l[1]-l[0])
for i in range(2, n):        
    gcd = math.gcd(abs(l[i] - l[i-1]), gcd)

for i in range(2, int(math.sqrt(gcd)) + 1):
    if gcd % i == 0:
        m.append(i)
        m.append(gcd//i)

m.append(gcd)
m = list(set(m))
m.sort()

for i in m:
    print(i, end=' ')

 

3. 풀이

생각보다 어려운 문제이다. 시간 초과가 나기 쉬워서 잘 고민하고 풀어야 한다.

최대공약수를 사용해야 한다.

 

숫자 N[0], N[1], N[2]가 있다고 했을 때, 

N[0] % M = N[1] % M = N[2] % M 인 M들을 우리는 찾아야 한다.

 

이 식을 조금 다르게 써보자. 여기서 Q는 몫을, R은 나머지를 의미한다.

M * Q1 + R = N[0]

M * Q2 + R = N[1]

M * Q3 + R = N[2]

이므로, R을 기준으로 써보자면

 

R = N[0] - M*Q1

R = N[1] - M*Q2

R = N[2] - M*Q3

이다.

 

N[0] - M*Q1 = N[1] - M*Q2

N[1] - M*Q2 = N[2] - M*Q3

이다.

 

 

N[0] - N[1] = M*Q1 - M*Q2

N[1] - N[2] = M*Q2 - M*Q3

여기서 식을 조금 더 정리해보자면,

N[0] - N[1] = M(Q1 - Q2)

N[1] - N[2] = M(Q2 - Q3)

위와 같이 된다.

 

즉, M은 N[0] - N[1], N[1] - N[2]의 공약수들이다. 그리고 이 공약수들은 최대공약수의 약수이다.

따라서 우리는 N[0] - N[1], N[1] - N[2], N[2]-N[3], ... 의 최대공약수를 구해, 그 최대공약수의 약수를 구하면 된다.

 

그리고 여기서 또 한 가지 포인트는,

최대공약수의 약수들을 구할 때, 최대공약수까지 반복문을 수행하는 것이 아니라 최대공약수의 제곱근까지 수행하는 것이다.

예를 들어 최대공약수가 14라면 14%2 = 0일 때, 2뿐만 아니라 14/2 = 7로 구해지는 7도 한 번에 결과리스트에 추가해주는 것이다.

이렇게 해야 시간이 훨씬 단축된다.