백준 2485 - 가로수 (파이썬)

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

풀이

가로수들이 일정하지 않은 간격으로 심어져 있다. 이 간격을 모두 같게 만들기 위해 새로운 나무들을 더 심어야한다.

• 현재 심어진 가로수의 좌표가 주어진다.
• 추가로 심어야 하는 나무의 수를 구하는 문제이다.

풀이과정은 다음과 같다.

1. 각 인접한 나무 사이의 간격을 구한다.
   1. 3 - 1 = 2, 7 - 3 = 4, 13 - 7 = 6
2. 이 간격들의 최대공약수를 구한다.
   1. 간격을 모두 gcd로 만들면 최소한의 나무로 균등 간격이 된다.
3. 전체 거리에서 gcd 간격으로 나무를 심었을 때의 전체 나무를 개산한다.
4. 기존에 있던 나무 수를 빼면, 추가로 심어야 할 나무 수가 나온다.

코드

# 백준 2485 - 가로수
# 분류 : 수학

N = int(input())
X = [0] * N

for i in range(N) :
    X[i] = int(input())

def gcd(a, b) :
    if a < b :
        a, b = b, a
    if b == 0 :
        return a
    else :
        return gcd(b, a % b)

d = 0
for i in range(N - 1) :
    d = gcd(d, X[i + 1] - X[i])

print((X[-1] - X[0]) // d + 1 - N)