백준 2981번 검문

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

2981번: 검문

문제

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

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

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

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

 

입력

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

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

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

 

출력

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

 

import sys

n = int(input())
num_list=[]
for i in range(n):
    num_list.append(int(sys.stdin.readline().strip()))

num_list.sort()

num_list = [num_list[i+1]-num_list[i] for i in range(len(num_list)-1)]
num_list = list(set(num_list))
def n_and_m(num, div):
    while True:
        temp = num % div
        if temp==0:
            return div
        else:
            num = div
            div = temp

gcd = num_list[0]
for i in range(1, len(num_list)):
    gcd = n_and_m(num_list[i], gcd)
result_list=[]
for i in range(2, int(gcd**0.5+1)):
    if gcd % i ==0:
        result_list.append(i)
        result_list.append(int(gcd/i))
result_list = list(set(result_list))
result_list.sort()
for i in result_list:
    print(i, end=" ")
print(gcd)

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

하지만 기존에 유사한 형태의 문제를 푼적이 없다면 쉬운 문제임에도 오랜 시간이 걸릴 수 있다.

 

한번 개념을 보기만해도 백준 17087과 같은 유사한 문제를 빠르게 풀 수 있기에 간단히 보고 넘어가는것 만으로 충분하다.

문제풀이

유클리드 호제법 보다는 이를 제외한 풀이를 해보겠다.

 

문제에서는 n개의 숫자가 같은 나머지를 같게되는 모든 수를 구해야 한다.

 

3개의 입력을 받았고 이를 큰 값부터 정렬했다고 가정할때 이를 식으로 표현하면 다음과 같다.

 

A = x * i + r

B = x * j + r

C = x * k + r 

 

 여기서 x를 구해야 하기 때문에 식을 변환해주면 아래와 같은 형태가 된다.

 

A - B = x * (i - j) + r

B - C = x * (j - k) + r 

 

C - A 와 같은 다른 조합은 정렬했을때  x가 음수이므로 고려할 필요가 없다.

 

이 개념에 추가적으로 구현시 몇가지 주의할 점이 있다.

1. 입력값의 범위가 크므로 x를 구한 다음 약수를 구할때 x의 제곱근 까지만 순회하면 몫과 인자를 결과에 넣어야 시간초과가 나지 않는다.

2. 입력값을 변환할때 중복된 값이 나올 수 있는데 이를 계산하는 것은 시간 낭비이므로 set(num_list)를 통해 실핼시간을 줄인다.

3. 1의 몫과 인자를 넣을때 제곱근일시 똑같은 값을 두번 넣게 되므로 set와 같은 방법으로 이를 추가적으로 제외시켜준다.