가로수 [백준 2485]

가로수들 사이 간격의 최대공약수를 구하면 쉽게 해결 가능하다. 

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

import sys
import math

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

input = sys.stdin.read
data = input().split()
n = int(data[0])
positions = list(map(int, data[1:]))

distances = [positions[i] - positions[i - 1] for i in range(1, n)]

current_gcd = distances[0]
for distance in distances[1:]:
    current_gcd = gcd(current_gcd, distance)

total_trees_to_add = 0
for distance in distances:
    total_trees_to_add += (distance // current_gcd) - 1

print(total_trees_to_add)