[python] 백준 2485 가로수

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

2485번: 가로수

 

 

문제 해결

• 각 나무 사이의 거리를 모아서 최대 공약수를 구한다.
• 최대 공약수를 나무와 나무 사이 거리로 생각하여 나무에서 최대 공약수만큼 떨어진 곳에 나무가 없으면 나무를 세우면 된다.

 

CODE

import sys
input = sys.stdin.readline
import math

n = int(input())
a = int(input()) # 첫 번째 나무 좌표

A = []

for i in range(n-1):
    num = int(input())
    A.append(num-a) # 나무와 나무 사이 거리
    a = num

g = A[0] # 첫 번째 나무와 두 번째 나무 사이 거리
for j in range(1,len(A)):
    g = math.gcd(g, A[j])
result = 0
for each in A:
    result += each//g -1
print(result)