[백준/2981] 검문 (with 파이썬)

✔ 문제

---

✔ 풀이

import sys
import math
input = sys.stdin.readline

n = int(input())
nums = [int(input()) for _ in range(n)]
nums.sort()
temp = []
res = []

for i in range(1, n): # A-B, B-C 저장
    temp.append(nums[i] - nums[i-1])

a = temp[0]
for i in range(1, len(temp)): # A-B, B-C 최대 공약수 구하기
    a = math.gcd(a, temp[i])

for i in range(2, int(a ** 0.5) + 1): # 탐색 범위를 줄이기 위해 제곱근 사용
    if a % i == 0:
        res.append(i)
        res.append(a // i)
res.append(a)

res = list(set(res))
res.sort()
print(*res)

---

✔ 설명

A = M * a + R

B = M * b + R

C = M * C + R

 

R을 제거하면

A - B = M(a - b)

B - C = M(b - c)

 

>> M은 A-B, B-C의 공약수이다  >> 최대 공약수를 구하면 됨

최대공약수를 구하고 해당 수의 1을 제외한 약수를 출력하면 된다.

---

✔ 후기

좀 어려운데 제대로 된 설명이 가능할까요 (つ﹏<｡ )

일단 다른 블로그를 통해서 어떤 공식이 정립되어야 하는지 확인했다.

뭔가 공식으로는 안써지고 머릿속에서만 나누기.. 나머지... 그걸로... 이런 상태로 부유하던 것들을 블로그 보니까 아 그래 이거구나! 싶은 마음이 들었다.

보고 풀긴 했지만 아직도 좀 어리둥절하다 (つ﹏<｡ )

 

 

참고 링크:

https://tmdrl5779.tistory.com/94

[백준] 2981번 (python 파이썬)