[구현/수학] 백준 2981 검문 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2981번: 검문

 

 

 

2. 문제 풀이

 N개의 수가 주어집니다. 이를 M으로 나누었을 때, 나머지가 모두 같아야 합니다. M은 1보다 크며, 가능한 모든 M을 출력해야 합니다.

 

입력: A, B, C

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

 위와 같이 A, B, C가 주어질 때, M으로 나눈 나머지는 모두 같아야 합니다. 하지만 이렇게 봐선 M을 찾기가 어렵습니다.

 

 

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

 나머지가 같으므로 빼주면, M에 관한 곱의 형태로 나타낼 수 있습니다. 두 수를 뺀 것들의 '최대 공약수'가 M이 되겠죠!

 한편 가능한 모든 M을 구하라고 했으니, 1을 제외한 M의 약수들을 구하면 됩니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
N = int(input())
numlist = []
for _ in range(N):
    numlist.append(int(input()))
numlist.sort()

# 유클리드 호제법
def gcd(a, b):
    if a < b:
        a, b = b, a
    while b != 0:
        a %= b
        a, b = b, a
    return a

# gcd 찾기
res_gcd = numlist[1] - numlist[0]
for i in range(1, N-1):
    res_gcd = gcd(res_gcd, numlist[i+1] - numlist[i])

 GCD는 math.gcd() 를 이용하셔도 좋고, 아래 링크의 유클리드 호제법을 사용해도 좋습니다. 저는 직접 구현해서 사용했습니다.

 

2022.02.05 - [Algorithm] - [Algorithm] 최대공약수(GCD) 구하기: 유클리드 호제법

[Algorithm] 최대공약수(GCD) 구하기: 유클리드 호제법

 

 

# gcd의 약수 찾기
divisor = set()
for i in range(1, int(res_gcd**0.5) + 1):
    if res_gcd % i == 0:
        divisor.add(i)
        divisor.add(res_gcd // i)
divisor.discard(1)

# 출력
print(" ".join(map(str, sorted(divisor))))

 GCD의 약수를 찾아줍니다. 2부터 M까지 1씩 올려가며 약수 판별을 할 수도 있지만, 시간초과가 날 수 있습니다. 그대신, M의 제곱근까지만 찾아줘도 됩니다. 자연수 n의 최대 약수는 루트 n 이하니까요. 왜 제곱근까지만 해도 되는지는, 아래 글에 증명해뒀습니다.

 

2022.02.08 - [Algorithm] - [Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체

[Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체