[백준] 2485 가로수

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

2485번: 가로수

임의의 간격으로 가로수가 심어져있다.

각 가로수의 간격이 같도록 가로수를 추가로 심어야 한다.

맨 처음 가로수의 수 N을 입력 받고 임의의 수를 번 입력한다. 이 때 맨 처음 입력한 수는 첫번째에 고정하고 맨 마지막에 입력한 수는 마지막에 고정한다.

N번 입력한 수를 already 리스트에 저장하고 이후 인덱스 - 이전 인덱스를 하여 간격을 구했다. 각 인덱스 마다의 간격을 gap_list리스트에 저장하였다.

0번째 리스트를 변수 n에 대입하고 gcd()함수를 통해 n과 gap_list인덱스와의 최대공약수를 구해 n에 새로 대입했다.

최대공약수를 간격으로 하며 맨 처음이 already[0]이고 맨 마지막이 already[-1]인 final 리스트를 생성했다.

(final리스트의 길이 - 기존에 심어진 가로수 already리스트의 길이)로 하니 메모리 초과가 발생하여 , 나무 간격을 최대공약수로 나눈 몫에 1을 빼어 심어야 하는 나무의 수를 구했다.

 

 

from math import gcd
 
N = int(input())  
 
already = [] 
for i in range(0,N):
    a = int(input())
    already.append(a)
 
gap_list =[]  
for i in range(0,len(already)-1):
    gap = already[i+1] - already[i]
    gap_list.append(gap)
 
 
n = gap_list[0]
final = []
for i in range(1,len(gap_list)): 
    n = gcd(n,gap_list[i])
final.append(n)
 
 
sum = 0
for i in range(0,len(gap_list)):
    a = (gap_list[i]//final[-1]) - 1
    sum += a
 
print(sum)