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

Interrobang 2023. 7. 14. 07:53

문제 링크

2485번: 가로수

첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가

www.acmicpc.net

문제 풀이

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

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