[백준] 15988. 123더하기 3 (9095번 연장)

9095번 123더하기와 문제는 똑같은데 n의 범위가 11에서 1000000으로 바뀌어서 메모리 초과, 시간 초과 오류에 시달렸다...

나의 해결방법은 nlist를 만들어 n의 값을 저장해 놓은 뒤 max(n)에 대한 dp list를 구해서 출력하는 것이다. 이중 for문을 피할 수 있음

import sys
t=int(sys.stdin.readline())
dp=[0]*1000001
dp[1]=1
dp[2]=2
dp[3]=4
n=[]
for i in range(t):
    n.append(int(sys.stdin.readline()))

for j in range(4,max(n)+1):
    dp[j]=(dp[j-1]+dp[j-2]+dp[j-3])%1000000009
for k in n:
    print(dp[k])