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

https://www.acmicpc.net/problem/15988

 

전에 풀었던 1,2,3더하기와 거의 일치한 문제

중간중간 나머지 연산과 시간초과로 인하여 처음부터 한번에 연산을 진행 후 마지막에 출력하는 형태로 변환

import sys
input = sys.stdin.readline
n = int(input())

dy = [0] * (1000001)
dy[0] = 1
dy[1] = 1
dy[2] = 2
dy[3] = 4
dy[4] = 7
dy[5] = 13
for i in range(5, 1000001):
        dy[i] = dy[i-1] % 1000000009 + dy[i-2]% 1000000009 + dy[i-3]% 1000000009

for i in range(n):
    a = int(input())
    print(dy[a] % 1000000009)

 

완성