[백준/Python] 2981번 - 검문

 

문제

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

 

트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다.

상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다.

먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다.

N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.

 

 

 

입력

 

첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100)

다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 같은 수가 두 번 이상 주어지지 않는다.

항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다.

 

 

출력

 

첫째 줄에 가능한 M을 공백으로 구분하여 모두 출력한다. 이때, M은 증가하는 순서이어야 한다.

 

 

풀이

 

유클리드 호제법

 

이 문제는 유클리드 호제법을 이용해서 푸는 문제다.

입력받은 수들을 나눴을 때, 나머지가 같은 수를 구하라고 했으므로, 입력받은 수들의 차를 유클리드 호제법을 이용하면 된다.

(입력 받은 수의 나머지가 r로 같다면 a = bq + r , a1 = b1q + r ... 과 같은 형태로 표현할 수 있다. 나머지인 r 이 같을 때 약수 q를 구하라 했으므로, 입력 받은 수들의 차를 구하면 c1 = a - a1 = (b - b1)q 로 표현할 수 있다.)

​

입력 받은 수들의 차들을 나열하면 c1 = d1q, c2 = d2q ... cn-1 = dn-1q 가 된다. (이때 dk >= 1, q는 입력받은 수들의 최대 공약수)

q를 구하기 위해서는 입력받은 수들의 차인 c를 이용해 임의의 ck와 나머지 cn들 간의 최대공약수를 유클리드 호제법으로 구하면 된다. (임의의 ck와 cn들을 비교해 그 중 가장 작은 최대공약수를 구하고, 최대공약수의 1을 제외한 약수들이 정답이다.)

이때, 구한 최대 공약수의 약수들을 구하기 위해서는 1부터 최대공약수 q의 제곱근까지만 약수를 계산하면 된다. (1 ~ q의 제곱근 사이의 약수 i를 이용하면 q//i를 활용해 동시에 구할 수 있음)

​

아래는 이를 코드로 구현한 내용이다.

 

 

Code

 

 

import sys
input=sys.stdin.readline

def gcd(a,b):
    global min_n #가장 작은 최대공약수를 저장할 변수
    if a<b:
        a,b=b,a
    c=a%b
    if c: # 나머지가 0이 아니면 다시 유클리드 호제법을 이용해 계산
        gcd(b,c)
        return
    if min_n>b:
        min_n=b
lst=[]
for _ in range(int(input())):
    lst.append(int(input()))
ans=[]
for i in range(len(lst)-1):
    ans.append(abs(lst[i+1]-lst[i])) #입력받은 수들의 차(모든 수들을 계산에 사용해야함)
ans.sort() #정렬을 해 주어야 수들 사이의 최대공약수를 구할 수 있다 
min_n=min(ans) #임의의 초기 값 설정 최대공약수는 min(ans) 보다 작으므로
for i in range(1,len(ans)): #하나의 차를 이용해 최대공약수들을 구하면 가장 작은 최대 공약수를 알 수 있음
    gcd(ans[0],ans[i])
l_ans=[]
for i in range(1,min_n+1):
    if not min_n%i:
        a=min_n//i
        l_ans.append(i)
        l_ans.append(a)
        if i>a:    # 제곱근 보다 크면 멈춘다
            break
r_l=list(set(l_ans)) # 중복제거
r_l.sort()
r_l.pop(0) # 약수 1제거
print(*r_l)

 

---

 

오랜만에 문제를 보니 흥미가 생겨 다시 풀었는데, 풀이에 이상한 부분을 발견해 고쳤다...

이상한 부분이 있어도 통과는 잘 됐는데;;

 

수학 공부를 따로 시작해야하나 생각이 든다...

 

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