[백준] 9095 - 1, 2, 3 더하기 [Python(파이썬)]

문제

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

풀이

유사한 문제들은 많이 풀어보았다.

1, 2, 3을 만들 수 있는 경우의 수를 dp테이블에 베이스로 저장해둔다. 

점화식은 다음과 같다.

dp[n] = dp[n-1] + dp[n-2] + dp[n-3] (3 <= n <= 11)

코드

import sys

t = int(sys.stdin.readline().strip())
dp = [0 for _ in range(12)]
dp[0:3] = [1, 1, 2]

for i in range(3, 12):
    for j in range(1, 4):
        dp[i] += dp[i-j]

for _ in range(t):
    n = int(sys.stdin.readline().strip())
    print(dp[n])