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

💡문제접근

• 시간초과(TLE)의 늪에서 빠져 헤어나오지 못했다. 문제는 간단하게 dp를 이용하는 문제였는데 시간초과의 원인은 아마 이중 for문을 통한 배열 선언이 아닐까싶다.
• 1,000,000보다 작거나 같은 배열을 만든 후 값이 엄청나게 커지는 것을 방지하기 위해서 1,000,000,009로 나눈 나머지를 저장한다.

💡코드(메모리 : 70452KB, 시간 : 436ms)

import sys
input = sys.stdin.readline

dp = [0 for _ in range(1000001)]
dp[0] = 1
dp[1] = 1
dp[2] = 2
# 이중 for문으로 하지 않고 한 번에 모두 선언
for i in range(3, 1000001):
    dp[i] = (dp[i-3] + dp[i-2] + dp[i-1]) % 1000000009

T = int(input().strip())
for i in range(T):
    n = int(input())
    print(dp[n] % 1000000009)

💡소요시간 : 10m