[백준] 2981 검문 (Python)

2981번: 검문

문제

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

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

먼저 근처에 보이는 숫자 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

 

---

 

문제 풀이

 

입력의 개수는 100으로 적지만, 각각의 입력이 십억까지도 가능하므로 이 문제는 2부터 N까지 확인해 보는 것이 아닌 다른 방법이 필요하다.

 

입력의 개수가 적으므로 입력 각각을 서로 비교하면 어떨까라고 생각했다.

 

x가 모든 수를 나눴을 때 모두 같은 나머지를 갖는다는 말은

A = ax + r 형태에서 r이 모두 같다는 말이 된다.

 

그렇다면

A = ax + r

B = bx + r

C = cx + r

에서 모든 수들을 서로 빼는 경우, 

 

A - B = (a-b)x

B - C = (b-c)x

로, x의 배수 형태가 나타나게 된다.

 

그럼 gcd((A-B),(B-C))로 x를 구할 수 있다.

---

 

코드

 

import sys
input = sys.stdin.readline


def gcd(b1, b2):
    while b2:
        b1, b2 = b2, b1 % b2
    return b1

N = int(input())
num_list = list(int(input())for _ in range(N))
num_list.sort()
sub_num_list = []
for i in range(N-1):
    sub_num_list.append(num_list[i+1]-num_list[i])

answer = sub_num_list[0]
for i in range(1, len(sub_num_list)):
    answer = gcd(answer, sub_num_list[i])

answer_set = set()
for i in range(2, int(answer**0.5)+1):
    if answer % i == 0:
        answer_set.add(i)
        answer_set.add(answer//i)
answer_list = list(answer_set) + [answer]
answer_list.sort()
print(*answer_list)

---

추가

 

A = ax+r 형태로 나오는 것과 r이 모두 같은 것, 그리고 각 원소들 사이의 관계를 비교해야 하는 것까지는 생각을 했으나 뺀다는 생각을 하지 못했다.

 

다음번에 비슷한 유형이 나온다면 단번에 쉽게 풀 수 있을 것 같다.