9095. 1,2,3 더하기

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

9095번: 1, 2, 3 더하기

 

일단 d[n]을 규정해보면

d[n] : n이라는 숫자를 1,2,3의 덧셈으로 만들 수 있는 총 가지 수

 

그렇다면 d[1] = 1

1

 

d[2] = 2

1 + 1,

2

 

d[3] = 4

1 + 1 + 1,

1 + 2,

2+ 1,

3

 

d[4] = 7

1 + 1 + 1 + 1, 1 + 2 + 1, 2 + 1 + 1, 3 + 1  // d[3]에서 1더함

1 + 1 + 2, 2 + 2  // d[2]에서 2 더함

1 + 3  // d[1]에서 1 더함

 

즉 d[4] = d[1] + d[2] + d[3] 이고

d[n] = d[n-3] + d[n-2] + d[n-1] 이다.

 

arr = [0] * 11


def dp(n):
    if n <= 2:  # base
        return n

    if n == 3:  # n == 3까지는 base 필요
        return 4

    if arr[n] > 0:  # memoization
        return arr[n]

    arr[n] = dp(n - 1) + dp(n - 2) + dp(n - 3)  # 점화식

    return arr[n]


t = int(input())  # test case

for j in range(t):
    x = int(input())  # input

    for i in range(x + 1):
        arr[i] = dp(i)

    print(arr[x])

 

 

// 추가

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;

    while(t--) {
        int n;
        cin >> n;
        int d[12];

        d[0] = 0;
        d[1] = 1;
        d[2] = 2;
        d[3] = 4;

        for(int i = 4; i <= n; i++) {
            d[i] = d[i-1] + d[i-2] + d[i-3];
        }

        cout << d[n] << '\n';
    }
}