★ BOJ : 2981 검문 (파이썬) ★

소스코드

import sys
import math

n = int(sys.stdin.readline())

lst = [] 

for i in range(n) :
    a = int(sys.stdin.readline())
    lst.append(a)

lst.sort()

gc = []

for i in range(len(lst)-1) :
    gc.append(lst[i+1] - lst[i])

gc.sort()
mini = gc[0]

for i in range(len(gc)-1) :
    mini = math.gcd(mini,gc[i+1])

result = []

for i in range(2,int(math.sqrt(mini)+1)) :
    if mini % i == 0 :
        result.append(i)
        if ((i**2) != mini) :
            result.append(mini//i)

result.append(mini)

result.sort() 

for i in result :
    print(i,end=' ')

 

풀이

매우 어려웠다.. 

맨처음 입력을 다 받아준 후 정렬을 해줍니다. 

그 후 리스트에 앞 뒤 수들을 빼줍니다. 그러면 그 뺀 수들로 새로운 리스트를 만들어줍니다.

x가 a라는 숫자에서 b 라는 숫자까지 얼만큼을 더해야하는지 값이라면, x = a - b 이고 모든 수들이 이런 관계를 가지게 되면 x들의 최대 공약수를 구하게 되면 같은 나머지를 구할 수 있게 됩니다. 

그 최대공약수에서 약수들을 새로운 배열에 담아 출력해주면 됩니다.

 

문제

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

2981번: 검문

 

반례

4
8
24
56
68
--------
2 4

5
9
17
31
45
69
--------
2