백준 15988 1, 2, 3 더하기 3

t = int(input())

def program(n):
    d = [1] * (n+1)
    d[2] = 2
    for i in range(3, n+1):
        d[i] = d[i-1] + d[i-2] + d[i-3]
    d[3] -= 1
    return d[n]    
for _ in range(t):
    n = int(input())
    if n == 1 or n ==2:
        print(n-1)
        continue
    print(program(n))

메모리 초과 코드 : 나누기를 안함

t = int(input())
mod = 1000000009
def program(n):
    d = [1] * (n+1)
    d[2] = 2
    for i in range(3, n+1):
        d[i] = (d[i-1] + d[i-2] + d[i-3])%mod
    d[3] -= 1
    return d[n]    
for _ in range(t):
    n = int(input())
    if n == 1 or n ==2:
        print(n-1)
        continue
    print(program(n))

시간 초과 코드 : 매번 d를 다시 계산하면 시간 너무 많이 걸림

t = int(input())
mod = 1000000009
d = [1] * (1000001)
d[2] = 2
def program(d, j, n):
    for i in range(j+1, n+1):
        d[i] = (d[i-1] + d[i-2] + d[i-3])%mod
    d[3] -= 1
    return d 
j = 2
for _ in range(t):
    n = int(input())
    if n == 1 or n == 2:
        print(n-1)
        continue
    if j < n:
        d = program(d, j, n)
        print(d[n])
        continue
    print(d[n])
    j = n

시간 초과 코드 : 나름 머리를 써봄. 계산횟수를 줄였는데 그다지 줄여지지 않은듯

d = [0] * 1000001
mod = 1000000009
d[0] = 1
for i in range(1, 1000001):
    if i >= 1:
        d[i] += d[i-1]
    if i >= 2:
        d[i] += d[i-2] 
    if i >= 3:
        d[i] += d[i-3]
    d[i] %= mod

t = int(input())
for _ in range(t):
    n = int(input())
    print(d[n])

먼저 d를 다 구하고 구함