[백준 - python] 2981번: 검문

Interrobang 2022. 11. 29. 12:13

문제 링크

2981번: 검문

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

www.acmicpc.net

문제 풀이

import math

n = int(input())
num, num2 = [], []

for i in range(n):
  num.append(int(input()))
  num.sort(reverse=True)

for i in range(len(num) - 1):
    num2.append(num[i] - num[i+1])

greatest_common_divisor = math.gcd(*num2)
ans = [greatest_common_divisor]

for i in range(2, int(greatest_common_divisor ** 0.5) + 1):
  if greatest_common_divisor % i == 0:
    ans.extend([i, greatest_common_divisor//i])
    
print(*sorted(list(set(ans))))

*key point: 주어진 조건을 만족하는 규칙을 찾는 것이 중요하다. 임의의 주어진 세 수 A, B, C는 (A > B > C라고 할 때) 문제의 조건을 만족하려면 아래와 같이 표현될 수 있다.

이때 A - B, B - C를 계산해보면 나머지와 상관없이 M이라는 수가 A - B, B - C의 공약수임을 알 수 있다.

이를 활용하여 주어진 입력값들로 새로운 수 리스트(A - B, B - C, ...)을 만들고 공약수를 찾으면 된다. 리스트에 *기호를 붙여 언패킹 할 수 있음을 활용하면 보다 간단한 코드를 짤 수 있다.