[Python] 2981번 : 검문

 

문제 3줄 요약

1. 상근이는 심심하다.

2. N개의 숫자가 종이에 있다.

3. 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게하는 M을 모두 찾아라

 

 

 

 

정수론 관련 문제는 딱 봐도

직관적으로 느껴지는게 없어서 힘든 것 같다..

(나는 그렇다. 다른 사람들은 직관적으로 보인다고 하더라)

 

저번 문제의 에라토스테네스의 체 같은 경우는

나름 이해하기 쉬웠지만,

이번엔 최대공약수를 구하는 "유클리드 호제법" 과 관련된 문제였다.

 

물론 위의 호제법을 몰랐기에

1부터 수를 늘려가며 비교해볼까 했지만,

당연하게도 수가 10억보다 같거나 작은 자연수기에 빠르게 포기하고

유클리드 호제법을 구글링하였다.

 

 

https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 나무위키

 

서로 나눈다해서

호제법이라고 불리며

나누어서 최대공약수를 구하는 알고리즘이다.

 

 

하지만 Python math 라이브러리에는

gcd라는 최대공약수를 구해주는 라이브러리가 있기에

선택하여 사용해주면 될 것 같다!

 

호제법 또는 gcd 함수로 최대공약수를 구한다치고,

 

근데 최대공약수는 왜 구하지???

 

 

질문게시판에서 서칭한 지식을

문제의 예시로 설명해보겠다.

 

Ex) 6, 34, 38인 경우 → 답 : 2,4 이다.

 

어떻게 2,4 가 나올까..?

결과부터 말하면 4의 약수인 1,2,4인데 1을 제외한다는 문제의 조건에 의해

2,4가 나온거다.

 

6, 34, 38의 최대공약수는 2인데,

왜 4의 약수를 구하냐?

 

 

이제부터 간단한 수학이 필요하다.

우리는 6, 34, 38에 공통으로 나눠줄 G와 나누어진 나머지 Y는 전부 같을거다.

여기서 G는 곧 우리가 알고싶은 값이 되겠다.

 

즉,

[A]     6 = x1 * G + Y,

[B]     34 = x2 * G + Y,

[C]     38 = x3 * G + Y 처럼 표현할 수 있다.

 

나머지인 Y가 뭐인지까진 구할 필요 없다.

그렇다면, 두 식을 묶어서 빼준다면 Y를 지울  수 있지 않을까?

 

음수가 생기지 않게

큰 수에서 작은수를 빼면,

[B- A]    28 = (x2-x1) * G,

[C - B]     4 = (x3-x2) * G,

[C - A]     32 = (x3-x1) * G 처럼 될 것이다.

빼서 Y를 지워준 것이다!

어렵지 않죠?

 

 

분명 G라는 변수 앞에 각 식을 만족시킬 값들이 있을 것이다.

하지만 우리가 알고싶은 것은

나눠줄 G 였다.

 

세 정수 4, 28, 32를 나누어 떨어지게 할 G는

바로 세 정수의 공약수들이다.

 

때문에 우린

최대공약수를 구해서,

1을 제외한 공약수들을 전부 구하려고 한 것!!

 

길었지만 요약하자면,

우리가 작성할 부분은

큰 수에서 작은 수를 빼주고

그 정수들의 최대공약수를 구해서 1을 제외한 공약수를 구한다!

 

from sys import stdin
from math import gcd

if __name__ == "__main__":
	# 종이에 적을 정수 개수
    N = int(stdin.readline())

    num_list = []
    for _ in range(N):
        num_list.append(int(stdin.readline()))

	# 큰 수에서 작은 수를 빼기 위해 오름차순
    num_list.sort()

    new_num_list = []

	# 정수의 차를 구한다.
    for i in range(len(num_list)):
        if i<len(num_list)-1:
            new_num_list.append(num_list[i+1] - num_list[i])
        else:
            new_num_list.append(num_list[i]-num_list[0])

	# 최대공약수를 갱신해주기 위해 오름차순으로 정렬
    new_num_list.sort()

	# 최대 공약수 
    min_gcd = new_num_list[0]
    for i in range(1,len(new_num_list)):
        min_gcd = gcd(min_gcd,new_num_list[i])

	# 중복과 1을 제외한 공약수들 구하기
    measure = set()
    for i in range(1,int(min_gcd**.5+1)):
        if min_gcd % i == 0:
            measure.add(i)
            measure.add(min_gcd//i)
    measure = measure - {1}
    
    # 정답 출력
    print(*sorted(list(measure)))

 

정수의 차를 왜 구해서

공약수를 찾는지 처음엔 이해가 되지 않았지만,

문제에 필요한 변수를 천천히 풀어 노트에 적다보니

이해하고 풀 수 있게 되었다.

 

역시 정수론 문제는

어렵다..

 

끝!