백준 2485번(silver 4) : 가로수 - 최대공약수

2485번: 가로수

---

 

 내가 작성한 코드 - 메모리 초과 

import sys
import math

input = sys.stdin.readline

n = int(input().rstrip())
tree = [int(input().rstrip()) for _ in range(n)]

# 심어진 나무들의 간격을 구하기
interval = []
for i in range(0, n-1):
    interval.append(tree[i+1]-tree[i])

# 간격들의 최대공약수 구하기
gcd = interval[0]
for j in range(1, len(interval)):
    gcd = math.gcd(gcd, interval[j])

# 심어야할 나무 위치 구하기
check = tree[0] + gcd
plant = []
for k in range(1, n):
    while tree[k] >= check :
        if tree[k] != check: # 만약 심어져 있어야할 위치에 나무가 없다면
            plant.append(check) # 그 위치 저장
        check += gcd # 다음 간격으로

# 심어야할 나무 개수 출력하기
print(len(plant))

 

처음에 어떻게 풀어야할지 몰라서 간격의 최대공약수를 구하면 된다는 것만 찾아보고 코드를 작성해보았는데 메모리 초과가 떴다.

그래서 풀이를 찾아보았다.

 

 

 심어야할 나무 구하고 출력하는 부분만 수정 

# 심어야할 나무 위치 구하기
plant = 0
for tree in interval:
    plant += tree // gcd - 1 # 최대공약수에는 1이 포함되므로 1을 뺴줘야한다.

# 심어야할 나무 개수 출력하기
print(plant)