[백준] #2981 검문 python

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

2981번: 검문

📕 설명 📕

시간 복잡도를 고려해야하는 문제이다.

 

먼저, 수학적 접근이 가장 필요하다.

 

M은 다른 수들 중 두 값을 뺀 값의 최대공약수이기 때문에 뺀 값의 최대 공약수를 구한다면 쉽게 구할 수 있다.

 

그리고, 공약수를 구할 때, 나눈 나머지 값이랑 몫 둘 다 공약수가 되기 때문에 이 둘을 다 고려해주면 복잡도를 대폭 낮출 수 있다.

🧑🏻‍💻 나의 풀이 🧑🏻‍💻

import math
N = int(input())

tmp_list = []
for i in range(N):
    tmp_list.append(int(input()))
tmp_list.sort()
interval_list = []
result_list = []

for i in range(1, N):
    interval_list.append(tmp_list[i] - tmp_list[i-1])

prev = interval_list[0]
for i in range(1, len(interval_list)):
    prev = math.gcd(prev, interval_list[i])

for i in range(2, int(math.sqrt(prev)) + 1):
    if prev % i == 0:
        result_list.append(i)
        result_list.append(prev//i)
result_list.append(prev)
result_list = list(set(result_list))
result_list.sort()
print(*result_list)