백준 2485 가로수

백준 2485 가로수

링크: 2485 가로수

---

접근 방법

• 간격을 파악 후, 간격들의 최대공약수를 구함
• 다수의 값에서 최대공약수를 구하는 것이 관건

---

소스 코드

소스 코드: 92571539 제출

import sys
from math import gcd
from functools import reduce

# 입력
N = int(sys.stdin.readline())
N_list = []
for _ in range(N):
    N_list.append(int(sys.stdin.readline()))

# 간격 계산
N_gap_list = [0] * N
for idx in range(N-1):
    N_gap_list[idx] = N_list[idx+1] - N_list[idx]

# 최대공약수 계산
gap = reduce(gcd, N_gap_list)
# print("gcd", gcd) # debug

# 출력
print((N_list[-1] - N_list[0])//gap + 1 - N)

---

결론

• 다수의 값에서 최대공약수를 구해야되는 문제는 처음 풀어봐서 많이 당황했다.
• math와 functools에 gcd와 reduce를 처음 알게 되어 공부가 필요할듯하다.