[Python] BOJ 2485 : 가로수

요구사항

1. 임의의 간격으로 심어져 있는 가로수 사이에 추가로 가로수들을 심어 연속된 가로수들 간의 차이가 일정하게 한다.
2. 새로 심어야 하는 가로수의 최소수를 구해라.

설계

1. 임의 설치된 가로수의 개수를 받는다.
2. 임의 설치될 가로수의 위치를 받는다. (양의 정수)
3. 연속되어 있는 가로수들 중 차이가 가장 적은 수를 구한다.
4. 첫 번째 가로수부터 다 더한다. 

위 설계의 예외

# 임의로 설치된 가로수
2 4 6 11

재설계

1. 설계의 1~2번 동일
2. 연속된 가로수들의 최대공약수를 구한다. 3과 5 의 최대공약수는 1 따라서 위 설계의 예외 시에도 가능하다. 
3. 새롭게 심을 가로수의 최소수는 아래 공식을 따른다.
4. (마지막 가로수 - 첫 번째 가로수) / GCD - (이미 심어진 가로수 - 1)
5. 결과를 출력한다.

정답 답안 예시

import sys, math
input = lambda: sys.stdin.readline().rstrip()

N = int(input())

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

distances = [trees[i] - trees[i-1] for i in range(1,N)]

gcd = distances[0]

for d in distances[1:]:
    gcd = math.gcd(gcd, d)

new_trees = (trees[-1] - trees[0]) // gcd - (N-1)

print(new_trees)