백준 2981번 검문 파이썬 (python code)

2981번

실버5

 

www.acmicpc.net/problem/2981

2981번: 검문

 

처음에는 for문을 최소화해서

for j in range(2,min(num[0]*2,num[1])-1):
    for i in range(N):

의 이중 for문으로 풀었는데 log n정도의 시간복잡도임에도 시간초과로 풀리지가 않아 수학적으로 접근했다.

 

A=P1*Q+R

B=P2*Q+R

C=P3*Q+R

등의 형태로 나타나는 수를 구하는데

R을 없애기 위해서 abs(A-B), abs(B-C)등의 표현을 사용했고

이 식들의 gcd를 구함으로서 최종 gcd를계산했다.

 

gcd를 이용해 약수를 계산하는데

전체를 다 계산하는것이 아니라

sqrt(gcd)+1까지만 계산해 추가하는 방식으로 시간을 줄였다.

def div(x):
    div_list = [x]
    for i in range(2, int(x ** (1 / 2) + 1)):
        if x % i == 0:
            div_list.append(i)
            if x // i != i:
                div_list.append(x // i)
    div_list.sort()
    return div_list

 

따라서 결과코드는

import sys
import math

def div(x):
    div_list = [x]
    for i in range(2, int(x ** (1 / 2) + 1)):
        if x % i == 0:
            div_list.append(i)
            if x // i != i:
                div_list.append(x // i)
    div_list.sort()
    return div_list

N = int(sys.stdin.readline())
w = [int(sys.stdin.readline()) for _ in range(N)]
wd = [abs(w[i] - w[i + 1]) for i in range(N-1)]

if len(wd) == 1:
    answer = wd[0]
else:
    answer = wd[0]
    for i in range(len(wd)):
        answer = math.gcd(answer, wd[i])
for i in div(answer):
    print(i, end=' ')