[백준 2981번] 검문(약수 알고리즘) in python

문제

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

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

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

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

입력

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

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

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

출력

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

예제 입력 1 

3
6
34
38

예제 출력 1 

2 4

예제 입력 2 

5
5
17
23
14
83

예제 출력 2 

3

---

이번 문제는 알아야 할 것이 많다.

 

먼저 나 혼자 끄적끄적 했던 코드를 보자면, m=2부터 시작해서 lst의 최댓값까지 하나씩 올라가는 코드이다.

이렇게 하면 결국은 답은 구할 것으로 예상한다. 하지만 입력의 조건을 보면 최대 십억까지의 숫자이다.

그만한 수를 다 풀기엔 시간초과가 날 것으로 예상했고 역시나 python3, pypy3 둘다 시간초과가 발생했다.

N=int(input())

lst=[int(input()) for _ in range(N)]

max_num=max(lst)
m_lst=[]
m=2
while m<max_num:
  k=lst[0]%m
  for n in lst[1:]:
    if k!= n%m:
      break
  else :
    m_lst.append(m)
  m+=1

print(*m_lst)

 

---

이제 검색해서 알아본 것을 정리해보자.

먼저 약수를 구하는 알고리즘부터 알아야 한다.

어떤 수에 대해 모든 약수들은 컬레값을 갖는다.

24의 약수들은 2, 3, 4, 6, 8, 12 총 6개이다. 이 친구들은 (2,12), (3,8), (4,6)으로 24가 된다.

즉 24를 2로 나눴을 때의 나머지가 0이라면 몫인 12도 약수인 것이다.

 

다음으로 N의 약수를 구할 때, N의 루트값+1까지 계산하는 것이 효율적이다.

또 예를 들자. 24의 루트는 4.~~~~일 것이다. 여기서 int를 취해서 4로 만들고 +1하면 5가 된다.

그럼 2부터 5까지만 24를 나누고 만약 나머지가 0이라면 몫과 나눈 값이 약수 값이다.

자 24를 2로 나눠보자. 그럼 약수는 2와 12가 나온다.

24를 3으로 나눠보자. 약수는 3과 8이 나온다.

24를 4로 나눠보자. 약수는 4와 6이 나온다.

24를 5로 나누자. 나머지가 0이 아니니 약수가 아니다.

 

이렇게 루트값+1까지만 찾아 계산을 해도 약수들을 다 찾을 수 있다! 모든 수가 다 이와같다!

---

 

다음으로 이제 진짜 이번 문제에 대해 살펴보자.

어떤 M으로 나눴을 때, 나머지가 같은 수를 찾는 것이다.

그럼 식으로 써보자.

lst=[n1,n2,n3]  이게 입력값.

m이 나누는 값.

 

식을 만들면, (s들은 몫, r은 나머지 : 나머지는 모두 같다는 가정)

n1=s1*m+r

n2=s2*m+r

n3=s3*m+r

이다.

여기서 r이 같다고 했으니 연립방정식으로 2개의 식을 만들어보자.

n2-n1=m(s2-s1)

n3-n2=m(s3-s2)

 

결국 s2-s1은 n2-n1의 약수임이 밝혀졌다.

s3-s2도 n3-n2의 약수임을 밝혀졌다.

 

여기서 s들을 구하지 말고 바로 n들의 값을 예로 들어보자.

예제의 6, 34, 38이 있다.

n3=38, n2=32, n1=6일 때 n2-n1=28, n3-n2=4가 된다.

여기서 m은 같으니깐> 28과 4의 최대공약수를 찾아주면 된다!

28과 4의 최대 공약수는 4인데, 4의 약수를 찾으면 2다. 그럼 최대공약수까지 함께 2,4가 28과 4의 약수 중 공통의 수가 되므로 이는 m이 된다.

N=int(input())
lst=[int(input()) for _ in range(N)]
lst.sort()

import math
gcd=lst[1]-lst[0]
for i in range(2,N):
  gcd=math.gcd(lst[i]-lst[i-1],gcd)

divisor_lst=[]
for i in range(2,int(gcd**0.5)+1):
  if gcd%i==0:
    divisor_lst.append(i)
    divisor_lst.append(gcd//i)

divisor_lst.append(gcd)
divisor_lst=list(set(divisor_lst))
divisor_lst.sort()

print(*divisor_lst)