[Baekjoon] #9095 - 1, 2, 3 더하기

⭐️ DP에서는 반복되는 부분을 찾아서 식으로 만들어내는 것이 중요하다.

⭐️ 문제에서 주어진 것을 100% 활용해야하고 반드시 작은 것부터 시도할 수 있는 부분까지 차근차근 적어보자

1 => 1 개	1
2 => 2개	1 + 1 2
3 => 4개	1 + 1 + 1  1 + 2  2 + 1  3
4 => 7개	1 + 1 + 1 + 1 1 + 1 + 2 1 + 2 + 1 2 + 1 + 1 2 + 2 1 + 3 3 + 1
5 => 13개	1 + 1 + 1 + 1 + 1 1 + 1 + 1 + 2 1 + 1 + 2 + 1 1 + 2 + 1 + 1 2 + 1 + 1 + 1 2 + 2 + 1 2 + 1 + 2 1 + 2 + 2 1 + 1 + 3 1 + 3 + 1 3 + 1 + 1 2 + 3 3 + 2

4를 만들 수 있는 1, 2, 3의 조합은 1을 만들 수 있는 조합의 개수 + 2를 만들 수 있는 조합의 개수 + 3을 만들 수 있는 조합의 개수이다.

5를 만들 수 있는 조합의 개수는 (2 + 3 + 4)를 만들 수 있는 조합의 개수이므로 점화식을 만들 수 있다.

 sol(n) = sol(n-1) + sol(n-2) + sol(n-3)

t = int(input())
s = []

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

for i in range(t):
    n = int(input())
    s.append(sol(n))

for i in s:
    print(i)