[파이썬] 백준 2981 검문

< 기존 풀이 > 

각 원소들의 차이를 이용한 계산까지는 생각을 했었다. 하지만 계속 시간 초과가 발생하였고 원인이 마지막 부분 약수 탐색 인 것을 발견하였다. 한번에 원소를 두 개 씩 넣어주면 되는데 난 두 배의 시간을 사용한 것이었다.

 

< 해결 방법 >

한번에 원소를 두 개 씩 넣어주는 방법을 사용해서 어렵지 않게 문제를 풀 수 있었다.

 

import sys
import math
 
a = sys.stdin.readline()
b = [ ]
c = [ ]
for i in range(0,int(a)):
    b.append(int(sys.stdin.readline()))
 
for i in range(0,len(b)-1):
    c.append(b[i+1]-b[i])
 
k = math.gcd(*c)
 
ans = [ ]
 
 
for i in range(1,int(math.sqrt(k))+1):
    if k%i==0:
        first = i
        second = int(k/i)
 
 
        if first == second:
            ans.append(first)
        else:
            ans.append(first)
            ans.append(second)
ans = sorted(ans)
for i in range(1,len(ans)):
    print(ans[i],end=" ")