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

문제

링크

코드

import sys
input = sys.stdin.readline

dp = [0, 1, 2, 4]

for i in range(4, 1000001) :
    dp.append((dp[i-1] + dp[i-2] + dp[i-3]) % 1000000009)
    
for _ in range(int(input())) :
    n = int(input())
    print(dp[n])

풀이

for i in range(4, 1000001) :
    dp.append((dp[i-1] + dp[i-2] + dp[i-3]) % 1000000009)

이 부분.. 처음에는 오래 걸릴까봐 1000001개 다 하기 보다는
조금씩 해야겠다~~
하고 재귀함수 써서 문제 풀었는데.. 재귀가 더 오래 걸릴 줄은 몰랐다 휴
눈물이?났지만?괜찮?습니다?

그리고 dp[i-1] + dp[i-2] + dp[i-3] 이렇게 세 개 더해주는 부분...
바보임
처음에 sum() 안에 넣어줬었음 뭐임 어쩐지 런타임에러 뜨더라
이런 실수... 앞으로 하지 않겟습니다.