[백준]9095 1, 2, 3 더하기 파이썬 python

문제링크

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

9095번: 1, 2, 3 더하기

코드

import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
    n = int(input())
    d = [0]*12
    d[1] = 1
    d[2] = 2
    d[3] = 4
    if n>3:
        for i in range(4,n+1):
            d[i] = d[i-1]+d[i-2]+d[i-3]
    print(d[n])
 

Point

 - 다이나믹프로그래밍으로 접근

 Subproblem 만족 & Optimal Substructure 

 

- 풀이 방법:

현재 할 수 있는 행동은 3가지 => +3 or +2 or +1