[알고리즘] 백준 15988 1, 2, 3 더하기 2 / 파이썬

www.acmicpc.net/problem/15988

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

 

#처음에 % 1000000009를 print에서 해줬는데 메모리초과 테스트케이스가 커지면 초과되는듯..?
lst = [0] * 1000001
lst[1], lst[2], lst[3] = 1, 2, 4
for i in range(4, 1000001):
    lst[i] = (lst[i-1] + lst[i-2] + lst[i-3]) % 1000000009
for _ in range(int(input())):
    num = int(input())
    print(lst[num])