[파이썬] 2981번. 검문 풀이

잘 생각해보자. N개의 주어진 수가 각각 A, B, C 라고 하자.

 

이때, 문제에 따르면 A, B, C를 이렇게 M으로 표현할 수 있다.

A = M x a(미지수인 몫) + R(항상 일정한 나머지)

B = M x b + R

C = M x c + R 

 

여기서 R을 제거하기 위해 A에서 B를, B에서 C를 뺀다고 하면 다음과 같은 식이 성립한다.

A - B = M(a - b)

B - C = M(b - c)

그렇다면 M은 A-B 와 B-C의 공약수이다.

 

이런 원리로, A~Z까지 입력받은 모든 수에 대해(오름차순), M은 B - A, C - B, ...... Z - Y의 공약수들이다.

즉, 이웃한 것끼리 뺀 수들의 최대공약수의, 1을 제외한 모든 약수가 M이 될 수 있는 것이다.

 

from math import gcd
from math import sqrt
import sys

N = int(input())

num_list = []
for _ in range(N):
    num_list.append(int(sys.stdin.readline().strip()))

num_list.sort()
sub_list = []
for i in range(N - 1):
    sub_list.append(num_list[i + 1] - num_list[i])

tour_gcd = sub_list[0] # N이 딱 2개인 경우, 두 수를 뺀 값이 단 하나의 M이기 때문이다.
for i in range(1, len(sub_list)):
    tour_gcd = gcd(tour_gcd, sub_list[i])

 

---

여기까지 최대공약수(tour_gcd)를 구했다. 이제 이 최대공약수의 1을 제외한 약수들이 문제를 만족하는 모든 M들이다.

하지만 문제의 입력은 10억을 넘어가기 때문에 일반적으로 약수를 구하면 시간복잡도가 증가한다.

 

이 때 약수를 구하는 반복문을 최대공약수의 제곱근(루트)만큼 줄일 수 있다.

예를 들어, 36의 경우 약수는 1 2 3 4 6 9 12 18 36 이다.

잘 보면, 제곱근인 6 이전의 모든 수에 대해, 1 x 36 = 36, 2 x 18 = 36, 이런 식으로 제곱근보다 큰 어떤 약수와 매칭되어 원래의 수를 이루기 때문에 그 두개의 수를 한번에 카운팅해주면 된다. 

 

divisor_list = []
for i in range(2, int(sqrt(tour_gcd)) + 1):
    if (tour_gcd % i == 0):
        divisor_list.append(i)
        divisor_list.append(tour_gcd // i)
divisor_list.append(tour_gcd)
# 마지막에 최대공약수 자기 자신도 추가해야 한다!

divisor_list = list(set(divisor_list)) # 리스트 중복 원소 제거
divisor_list.sort()

print(*divisor_list) 
# Asterisk(*)의 기능 중 하나는 컨테이너 타입의 데이터를 Unpacking 할 수 있다.

 

https://www.acmicpc.net/problem/2981

2981번: 검문