9095 - 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

 

import sys
input = sys.stdin.readline

def funcdp(i):
    dp = [0] * (i+3)
    dp[1] = 1
    dp[2] = 2
    dp[3] = 4

    if i <= 3:
        return dp[i]
    
    for x in range(4, i+1):
        dp[x] = dp[x-1] + dp[x-2] + dp[x-3]

    return dp[i]

t = int(input())
for _ in range(t):
    n = int(input())
    print(funcdp(n))

 

- Dynamic Programming

 

헤헤 디피 재밌다