BOJ 9095번: 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

이것도 꽤 자주? 접했던 유형의 문제였다.

n을 1, 2, 3의 합으로 나타내야 할 때 가능한 경우는 n-1 + 1 , n-2 + 2, n-3 + 3의 세 가지 경우이므로 

dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 로 구할 수 있다.

초기값

dp[1] = 1 //1

dp[2] = 2 // 2, 1+1

dp[3] = 4 //3, 2+1, 1+2, 1+1+1

 

import sys
input = sys.stdin.readline

T = int(input())
dp = [0] * 11
dp[0] = 1
dp[1] = 2
dp[2] = 4

for i in range(3, 11):
    dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    
for _ in range(T):
    n = int(input())
    print(dp[n-1])