[백준 - python] 2981번: 검문

문제 링크

2981번: 검문

문제 풀이

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))))

2981 입출력 예시

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

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

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