[백준] 2981번 검문 (Python)

백준 2981 검문

정수론이라는 것은 알았지만 풀이가 쉽게 떠오르지 않았던 문제다. 점화식을 적어보면서 풀이를 떠올리면 구현하는 것은 쉽지만, 아이디어를 떠올리기가 조금 힘들었다.

$A = Qa + M$
$B = Qb + M$
$C = Qc + M$

일 때, M을 제거해야 문제 풀기가 수월해진다는 것을 알 수 있었야 한다. M을 하나하나 찾을 필요 없이, 뺄셈을 활용해 나머지를 제거할 수 있다.

$A - B = Q(a - b)$
$B - C = Q(b - c)$

이고, 여기서 Q의 값은 각 숫자를 뺀 값들의 최대공약수의 약수라면 모두 가능하다는 것을 알 수 있다. 약수를 구하는 과정은 최대공약수의 제곱근까지의 숫자를 탐색하며, $T = ab$라면 a 와 b를 모두 정답 리스트에 넣어 해결할 수 있다. 단, 위 식에서 a 와 b는 같을 수도 있기 때문에, set()을 활용해 중복을 방지하고, 1은 마지막에 set에서 제거해 줘야 한다.

1. interval에 모든 입력값의 차를 저장
2. interval의 모든 수의 최대공약수 탐색
3. 최대공약수의 약수(1을 제외)를 정렬하여 반환

import sys
from math import gcd
from math import sqrt

input = sys.stdin.readline
n = int(input().strip())
nList = sorted([int(input().strip()) for _ in range(n)])
interval = [nList[i + 1] - nList[i] for i in range(n - 1)]
res = set()

greatestCD = interval[-1]
for i in range(n - 2):
    greatestCD = gcd(greatestCD, interval[i])
for div in range(1, int(sqrt(greatestCD)) + 1):
    q, r = divmod(greatestCD, div)
    if r == 0:
        res.add(q)
        res.add(div)
res.remove(1)
print(*sorted(res))