[백준 - python] 2485번: 가로수

문제 링크

2485번: 가로수

문제 풀이

from sys import stdin
from math import gcd

input = stdin.readline

n = int(input())
location = [int(input()) for _ in range(n)]
length = [location[i + 1] - location[i] for i in range(len(location) - 1)]

g = gcd(*length)

print(sum([len // g - 1 for len in length]))

2485 입출력 예시

*key point: 각 가로수 사이 길이의 최대공약수를 구하고 각 길이에서 나누어 새롭게 만들어지는 간격의 개수를 구한다. 각 간격을 만들기 위해서는 간격의 수 -1 만큼의 나무가 필요함에 유의한다. 또한, 시간을 단축하기 위해 sys, math 모듈을 활용한다.