[백준] 2485번 가로수

💡문제접근

각 가로수의 위치의 간격을 구한 다음 간격의 최대공약수를 구하고 각 간견을 비교해서 심을 가로수의 최소수를 구하는 방식으로 코드를 작성했다.

💡코드(메모리 : 123856KB, 시간 : 160ms, PyPy3로 제출)

import sys
import math

N = int(input())
colonnade_interval = []
for _ in range(N):
    colonnade_interval.append(int(sys.stdin.readline().strip()))

colonnade_interval.sort()
gap = []
for i in range(N-1):
    gap.append(abs(colonnade_interval[i] - colonnade_interval[i+1]))

gcd = gap[0]
for i in range(1, N-1):
    gcd = math.gcd(gcd, gap[i])

count = 0
for i in range(N-1):
    if abs((colonnade_interval[i] - colonnade_interval[i+1]) // gcd) == 1:
        continue
    else:
        count += abs((colonnade_interval[i] - colonnade_interval[i+1]) // gcd) - 1
print(count)

💡소요시간 : 27m