[Baekjoon] 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

문제 풀이

# 최대공약수 # 약수

문제를 보자마자 떠오른 풀이는 ‘m을 1씩 증가시켜가며 모든 n을 m으로 나눈 나머지가 모두 같은 지 매번 검사’하는 풀이였습니다.

하지만 이 풀이의 시간 복잡도는 O(N*M) 이기 때문에 시간초과로 통과할 수 없습니다. (N은 n의 개수, M은 m의 범위)

👍 1번 풀이(시간 초과)

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

from math import gcd
m = 1
while m < nums[-1]:
    m += 1
    mod = nums[0] % m
    for i in range(1,len(nums)):
        if nums[i] % m != mod: break
    else: print(m,end=' ')

그래서 고민에 고민을 거듭한 결과…

입력으로 주어지는 수들의 차이에 집중해봤습니다.

그리고 이는 수식으로 나타내면 그 관계가 자명해집니다.

모든 수 n을 m으로 나눈 나머지가 k로 같다면,

n1 / m = p1 … q, n2 / m = p2 … q ➡ n1 = m * p1 + k, n2 = m * p2 + k

두 수식을 빼면,

|n1 - n2| = m * |p1 - p2|

따라서 n1과 n2가 같은 나머지를 가지는 수 m은 n1과 n2의 차의 약수입니다.

따라서 모든 n에 대하여 숫자의 차들의 최대 공약수를 구하고, 이 최대 공약수의 약수를 구함으로써 답을 구할 수 있습니다.

👍 2번 풀이

N = int(input())
nums = [int(input()) for _ in range(N)]
# 수들의 차
diffs = [abs(nums[i]-nums[i-1]) for i in range(1,len(nums))]
# 차들의 최대 공약수
from math import gcd
_gcd = gcd(diffs[0],diffs[-1])
for diff in diffs:
    _gcd = gcd(_gcd,diff)
# 최대 공약수의 약수
ans = set([_gcd])
for n in range(2,int(_gcd**(1/2))+1):
    if _gcd % n == 0:
        ans.add(n)
        ans.add(_gcd//n)
        
print(*sorted(list(ans)))