백준 2981번: 검문 (Python)

접근

최대공약수를 이용하는 문제이다.

세개의 수 A, B, C가 M으로 나누었을 때 나머지 R을 가질 경우 다음과 같이 표현할 수 있다.

A = M * a + R
B = M * b + R
C = M * c + R

이 때, 첫째 줄에서 두번째 줄을, 그리고 두번째 줄에서 세번째 줄을 빼면 다음과 같이 나온다.

A - B = M * (a - b)
B - C = M * (b - c)

A - B와 B - C는 M을 공약수로 가지게 되며, 두 수의 최대공약수를 LCM이라고 할 때, LCM의 약수들은 모두 M이 될 수 있다. 즉 N개의 숫자가 주어질 경우, A-B, B-C 등 N[i] - N[i - 1]은 N - 1개의 숫자로 나타게 되며, N - 1 개의 숫자들의 최대공약수를 구하고, 이 최대공약수의 약수들을 오름차순으로 표시함으로써 정답을 구할 수 있다.

코드

import sys

n = int(sys.stdin.readline())
num = []
for i in range(n):
    num.append(int(sys.stdin.readline()))
gcds = [abs(num[1] - num[0])]


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


for j in range(2, len(num)):
    gcds.append(gcd(abs(num[j] - num[j - 1]), gcds[0]))
gcds.sort()
ans = []
for k in range(1, int(gcds[0] ** 0.5) + 1):
    if gcds[0] % k == 0:
        ans.append(k)
        ans.append(gcds[0] // k)
ans = list(set(ans))
ans.sort()
for l in ans[1:]:
    print(l, end=" ")

더 생각해 볼 것?

이상하게 주어지는 숫자가 오름차순으로 주어진다고 착각하는 바람에 인덱스에러(TypeError)가 여러번 떴다. 문제를 제대로 파악하도록 해야겠다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!