[백준] 2485번 가로수 파이썬 코드

코드

from math import gcd
n = int(input())
num = [int(input()) for _ in range(n)]
rksrur = []
for i in range(n-1):
  rksrur.append(num[i+1]-num[i])
maxrksrur = gcd(*rksrur)

cnt = 0
for i in rksrur:
  cnt += i//maxrksrur-1
print(cnt)

가로수의 간격 // 최대공약수를 해서 구하는 방법이 아니면 메모리 초과나 시간 초과의 벽에 부딪히게 된다. 나누는 방법을 이용하면 O(N)의 복잡도로 해결할 수 있다.