[파이썬/python] 백준 2485번 : 가로수(🥈4)

https://www.acmicpc.net/problem/2485

import sys
input = sys.stdin.readline
from math import gcd

n = int(input())
trees = []
gap = []

for i in range(n):
    trees.append(int(input()))
    if i > 0:
        gap.append(trees[i] - trees[i-1])

a = gcd(gap[0], gap[1])
for i in range(1, n-1):
    a = gcd(a, gap[i]) 

print((trees[-1]-trees[0]) // a + 1 - n)

처음에 제일 큰 gap이랑 제일 작은 gap의 최대공약수만 구하면 된다고 생각해서 틀렸다

만약 4,6,8 일 경우에는 4와 8의 최대공약수는 4이기 때문에 오답이 나온다.. 바보였다

그래서 계속 갭과 그다음갭의 최대공약수, 그다음갭과 그다다음갭의 최대공약수를 계속 업데이트해 주는 식으로 최대공약수를 구하면 보든 갭의 최대공약수가 나온다.

그리고 나무의 제일 마지막위치와 처음 위치의 차를 구한 후, 최대공약수로 나눈 다음 1을 더하면 나무의 총개수가 나온다.

총개수에 n을 빼주면 비어있는 나무의 개수가 나온다.