[백준] 15988번_1,2,3더하기3

문제 링크 : https://www.acmicpc.net/problem/15988

15988번: 1, 2, 3 더하기 3

d = [0]*1000001
d[0]=1;d[1]=1;d[2]=2
for i in range(3,1000001):
    if d[i]==0:
        d[i] = d[i-1]+d[i-2]+d[i-3]
        d[i] %= 1000000009
for _ in range(int(input())):
    n = int(input())
    print(d[n])

앞선 문제와 비슷하지만 n의 범위가 커짐에 따라 미리 입력값n을 받기 전, 다 구했다.