(파이썬) 백준 2981번 "검문" 자세한 원리

---

# 답

import math

N = int(input())
arr = []
G = 0

for i in range(N):
    arr.append(int(input()))
    if i == 1:
        G = abs(arr[1] - arr[0])
    G = math.gcd(G, abs(arr[i] - arr[i - 1]))

# G의 약수 구하기
ans = set([G])
for i in range(2, int(G ** 0.5) + 1):
    if G % i == 0:
        ans.add(i)
        ans.add(G // i)

print(*sorted(list(ans)))

 

 

 

 

---

# 원리

 

나누었을 때 나머지(R)를 모두 같게 만들어주는 숫자 M이 있다고 가정해봅시다.

그렇다면 각 숫자들(N)은 아래와 같이 표현할 수 있을 것입니다.

 

N[0] = X[0] * M + R

N[1] = X[1] * M + R

N[2] = X[2] * M + R

 

               ↓

 

N[0] - R = X[0] * M

N[1] - R = X[1] * M

N[2] - R = X[2] * M

 

 

즉, 다음 세 숫자      N[0] - R  ,   N[1] - R  ,   N[2] - R     는 M이라는 공약수를 갖게 됩니다.

가능한 모든 공약수 M을 구하기 위해서는, 위 세 숫자들의 최대공약수 G의 약수를 구하면 됩니다.

 

나머지 R은 최소 0부터 최대 min(N[0], N[1], N[2]) - 1까지 가능합니다.

그러니, R에 0부터 가능한 모든 값들을 모두 대입해보고 각 경우에 대한 최대공약수를 구한다면 이 문제를 풀 수 있습니다.

하지만 이렇게 풀면 시간이 너무 오래 걸립니다. 따라서 유클리드 호제법을 이용하여 시간을 단축해야합니다.

 

 

 

 

유클리드 호제법이란 다음과 같습니다.

"어떤 수 a와 b가 있을 때(a > b), a와 b의 최대공약수는 a를 b로 나눈 나머지 r과 b의 최대공약수와 동일하다."

 

이 때 r이라는 숫자는 어떻게 해서 구해지는 건지 잘 생각해봅시다.

a에 계속해서 b를 빼다가 남은 값이 나머지 r 아닌가요?

 

따라서 유클리드 호제법을 다음과 같이 확장할 수 있습니다.

"어떤 수 a와 b가 있을 때(a > b), a와 b의 최대공약수는 a - b와 b의 최대공약수와 동일하다."

 

실제로 증명도 가능합니다.

a와 b의 최대공약수를 G라고 한다면 아래와 같이 표현할 수 있습니다.

 

a = x * G

b = y * G

 

    ↓

 

a - b = G * (x - y)

 

따라서 a - b 또한 G를 공약수로 가지게 됩니다.

 

다시 문제로 돌아가서, 우리는 다음 세 숫자 N[0] - R  ,   N[1] - R  ,   N[2] - R  에서 R값을 달리하여 최대공약수를 각각 구하는 게 목적이었죠?

하지만 유클리드 호제법을 안다면 R값을 일일이 바꿔가며 풀 필요가 없습니다. 어떤 숫자들의 최대공약수는, 서로를 빼 준 숫자들의 최대공약수와 동일하기 때문입니다. 즉,

 

N[0] - R

N[1] - R

N[2] - R

의 최대공약수는

 

N[0] - R - (N[1] - R)

N[1] - R - (N[2] - R)

N[2] - R - (N[0] - R)

 

↓

 

N[0] - N[1]

N[1] - N[2]

N[2] - N[0]

의 최대공약수와 동일합니다.

R이 모두 소거되기 때문에, 훨씬 수월하게 정답을 구할 수 있게 됩니다.

 

이 문제를 한 마디로 요약하자면 이렇게 말할 수 있겠네요

이 문제의 정답은 "((이웃한 수들의 차)들의 최대공약수)의 약수"입니다.