[백준_15988] 1, 2, 3 더하기 3 python

처음 문제를 풀었을 때 메모리 초과에 걸렸다.

왜일까 고민하다가 '방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.'에서 힌트를 얻었다.

디피를 채울 때 나머지만 넣어 줘도 상관이 없지 않을까 하는 생각을 했다.

근데 난 이 디피가 어떻게 이루어졌는지 잘 모르겠다.

# dp 설계
dp = [
    0 for _ in range(1000001)
]

# dp 초기설정
dp[1] = 1
dp[2] = 2
dp[3] = 4

# dp 채워넣기
for i in range(4, 1000001):
    dp[i] = (dp[i-3] + dp[i-2] + dp[i-1]) % 1000000009

# t 입력
t = int(input())

# n 입력
for _ in range(t):
    
    n = int(input())

    print(dp[n] % 1000000009)