BOJ 2981 : 검문

문제

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

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

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

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

풀이

아래 블로그를 참고하였다.

https://velog.io/@ledcost/%EB%B0%B1%EC%A4%80-2981-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EA%B2%80%EB%AC%B8-%EA%B3%A8%EB%93%9C5-%EC%A0%95%EC%88%98%EB%A1%A0

[백준 2981 파이썬] 검문 (골드5, 정수론)

이 문제는 앞서 풀었던, 최대공약수, 최소공배수 등의 아이디어인 유클리드 호제법의 응용이다. 아래 그림을 예시로 하여 풀이법을 참고했다.

아래와 같이 M을 포함하는 수를 정의했을 때,

A = M * a + R

B = M * b + R

C = M * c + R

 

나머지 R을 없애려면, 두 수의 차를 계산하면 된다.

 

B - A = M(b-a)

C- B = M(c-b)

 

이때, 두 수의 차의 최대공약수를 구했을 때, 그것의 약수들이 M이 될 수 있다. 가능한 M은 그렇게 구해지며 코드는 다음과 같다.

import sys
import math

def div(x):
    div_list = [x]
    for i in range(2, int(x ** (1 / 2) + 1)):
        if x % i == 0:
            div_list.append(i)
            if x // i != i:
                div_list.append(x//i)
    div_list.sort()
    return div_list

if __name__ == '__main__':
    N = int(input())
    
    data = [int(sys.stdin.readline()) for _ in range(N)]
    data_d = [abs(data[i] - data[i+1]) for i in range(N-1)]

    answer = data_d[0]
    if len(data_d) > 1:
        for i in range(len(data_d)):
            answer = math.gcd(answer, data_d[i])
    for i in div(answer):
        print(i, end = ' ')

여기서 범위가 왜 GCD의 제곱근이 되는지 궁금했었는데, 36이 GCD가 되었다고 하면.. 2*18과 18*2는 같다. 따라서 6*6인 범위의 수 내부에서 찾기만 하면 된다. 시간 초과를 피하기 위한 아이디어 이지만, 이왕 코딩하는 김에 시간 단축할 수 있는 아이디어로서 충분히 좋은 것 같다.