[백준_python] 1, 2, 3 더하기 || 9095

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

이 문제 또한, 다이나믹 프로그래밍 문제이다.
1 : (1)
2 : (1, 1) (2)
3 : (1, 1, 1) (1, 2) (2, 1) (3)
4 : (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (2, 1, 1) (1, 3) (3, 1) (2, 2) → 7개
5 : (1, 1, 1, 1, 1) (1, 1, 1, 2) x 4 (1, 1, 3) x 3 (2, 3) x 2 (1, 2, 2) x 3  → 13개 = 7 + 4 + 2
6 : (1, 1, 1, 1, 1, 1) (1, 1, 1, 1, 2) x 5 (1, 1, 1, 3) x 4 (1, 1, 2, 2) x 6 (2, 2, 2) (1, 2, 3) x 6 (3, 3) → 24개 : 13 + 7 + 4
따라서, 점화식은 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 이다.

# 1, 2, 3 더하기

def dp(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    else:
        return dp(n-1) + dp(n-2) + dp(n-3)


T = int(input())
for _ in range(T):
    n = int(input())
    print(dp(n))