문제출처 : https://www.acmicpc.net/problem/2485

풀이과정

1. 주어진 나무 사이의 거리를 distance리스트에 담는다.

2. distance리스트의 숫자들의 최대공약수를 구한다.(사이사이에 나무를 심기 때문에)

3. 처음 나무와 마지막 나무 사이의 총거리를 최대공약수로 나눠주고 + 1 해준 값(최대공약수 만큼의 거리를 둔 새로운 나무 수)에 원래 나무수를 빼준다.

import math
import sys
input = sys.stdin.readline


def howManyTree(myInput) :
    distance=[]
    for i in range(len(myInput)-1):
        distance.append(myInput[i+1]-myInput[i])
    
    gcd = math.gcd(distance[0],distance[1])
    
    for i in range(2,len(distance)):
        gcd = math.gcd(gcd,distance[i])

    return print(int((myInput[-1]-myInput[0])/gcd) + 1 - len(myInput))

n = int(input())
myInput=[]
for i in range(n):
    myInput.append(int(input()))

howManyTree(myInput)

처음에는 answer라는 새로운 나무들의 위치 리스트를 만들었는데 메모리 초과로 실패가 떠서 코드를 새로 짜게 되었다.