[boj] 백준 15988 1, 2, 3 더하기3 python 풀이

ex) 4의 경우

3에서 가능한 모든 경우의 수에 +1을 더하는 경우가 더해짐

1+1+1 +1, 2+1 +1, ...

이런식..

 

근데 1, 2, 3을 더할 수 있으니 dp[i-1], dp[i-2], dp[i-3]을 모두 더해주면 모든 경우의 수를 고려하게 되는 것

 

문제

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

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

 

풀이

import sys
input = sys.stdin.readline

T = int(input().strip())

dp = [1, 2, 4]

def fill_dp(dp, n): 
    idx = len(dp)-1
    while idx<n:
        num = (dp[-3] + dp[-2] + dp[-1])%1000000009
        dp.append(num)
        idx += 1


for _ in range(T):
    n = int(input().strip())

    try:
        print(dp[n-1])

    except:
        fill_dp(dp,n)
        print(dp[n-1])