[백준/Python] 2485 가로수

[백준/Python] 2485 가로수

def gcd(a,b):
    while b!=0:
        a, b = b, a % b
    return a 

n = int(input())
trees = [int(input()) for _ in range(n)]

intervals = [trees[i+1] - trees[i] for i in range(n-1)]

ideal_interval = intervals[0]
for interval in intervals[1:]:
    ideal_interval = gcd(ideal_interval, interval)

new_trees = 0
for interval in intervals:
    new_trees += (interval // ideal_interval) - 1

print(new_trees)

위 문제를 풀기 위해선
1. 모든 인접한 가로수 사이의 간격을 저장하고 간격의 최대 공약수를 찾는다. 새로운 가로수를 심어야 할 이상적인 간격을 뜻한다.
2. 새로 심어야 하는 가로수의 수 계산 : 이상적인 간격을 바탕으로 현재 가로수 사이의 간격을 나누어 새로 심어야하는 가로수를 계산한다.

[코드 내용 설명]
1. 일단 가로수 수를 입력받고, 가로수가 심어진 위치를 리스트에 저장한다.
2. intervals 이라는 변수에 모든 가로수에 대해 인접한 가로수 사이의 간격을 계산해서 저장한다.
3. 모든 간격에 대해서 최대 공약수를 찾고 이를 ideal_interval 로 지정하자
4. 새로 심어야 하는 가로수 수를 계산한다.