문제

입력 , 출력

정답

import sys

n = int(input())
arr = [0 for j in range(1000001)]
arr[0] = 1
arr[1] = 1
arr[2] = 2
for i in range(3, 1000001):
    arr[i] = arr[i - 1] % 1000000009 + arr[i - 2] % 1000000009 + arr[i - 3] % 1000000009
for i in range(n):
    a = int(input())
    print(arr[a] % 1000000009)

설명

점화식이 arr[i-1] + arr[i-2] + arr[i-3] 이 나왔는데
문제를 다 풀었는데 메모리초과가 나와서 검색을 해보니
arr[i -1] 을 더할때 % 1,000,000,009 을 해주니 메모리 초과가 안났다.

후기

전에 풀었던 1,2,3 더하기와 비슷해서 금방 풀었지만
메모리 초과가 나서 시간을 10분정도 먹은거같다...
단위체크를 잘하자!