백준) 2981 - 검문 [파이썬3]

문제)

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

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

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

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

 

입력)

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

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

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

 

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

---

import math

num = sorted([int(input()) for _ in range(int(input()))])
dif = [num[i] - num[i-1] for i in range(1, len(num))]

gcd = dif[0]
for i in range(1, len(dif)):
    gcd = math.gcd(gcd, dif[i])

result = [str(gcd)]
for i in range(2, int(gcd ** (1/2)) + 1):
    if gcd % i == 0:
        result.append(str(i))
        result.append(str(gcd // i))
print(' '.join(sorted(list(set(result)), key = lambda x : int(x))))

풀이)

 문제를 이해하기 위해 식을 간단하게 적어보았다. 이 때, 몫은 a, 나머지는 R이라고 해보았다.

N₁ = M * a₁ + R

N₂ = M * a₂ + R

N₃ = M * a₃ + R

....

N_n = M * a_n + R

문제에서 요구하는 것은 조건을 만족하는 모든 M을 구하는 것이다. 각 수식에서 R을 없애기 위해서 (i + 1)항에서 (i) 항을 뺀 뒤 수식을 정리해보면 아래와 같이 정리된다. (1 ≤ i ≤ n-1)

N₂ - N₁ = M * (a₂ - a₁)

N₃ - N₂ = M * (a₃ - a₂)

....

N_n - N_n-1 = M * (a_n - a_n-1)

여기서 알 수 있는 것은 (i+1) - (i) 의 집합들에 M이 약수로 사용되었다는 것이다. 즉, 새롭게 정의된 집합내의 최대 공약수를 알면 문제를 해결할 수 있다는 뜻이다.

 최대공약수(gcd)를 구한 뒤 gcd의 약수들이 문제에서 요구하는 답이다. 이 때, 2부터 gcd까지를 범위로 지정하여 for문을 사용할 경우 시간초과가 날 수 있기에 gcd의 제곱근 까지만을 범위로 지정해준 뒤, 해당 범위 내에서

(a 가 A의 약수일 경우 A를 a 로 나누었을 때의 몫 b도 A의 약수이다 => A = a * b) 의 성질을 이용하여 약수를 모두 구해줄 수 있다.

 

ps1. join을 이용하여 결과를 출력할 때 join에 사용되는 리스트 속 데이터 타입은 모두 str이어야한다. 그렇기 때문에 result 리스트에 결과를 저장해 줄 때, str()로 데이터 타입을 변경하여 저장해주었다.

 

ps2. 데이터를 정렬할 때, 정렬되는 데이터가 str일 경우 맨 앞자리를 우선적으로 기준으로 판단한다. 만약 1, 2, 3, 10, 20 이 입력이라면 정렬 후 결과각 1, 10, 2, 20, 3이 된다. 그렇기 때문에 sorted함수를 사용할 때 key로 int(x)값을 사용하였다.