[C++] 백준 BOJ 9095 1,2,3 더하기

문제링크 : https://noj.am/9095

어떤 숫자 N을 1, 2, 3 더하기로 나타내는 방법은 다음과 같다.

[1] - 1개

1

[2] - 2개

1+1 → [1]+1

2

[3] - 4개

1+2 → [1]+2

1+1+1, 2+1 → [2]+1

3

[4] - 7개 (1+2+4)

1+3 : [1]+3 → [1] + 3

1+1+2, 2+2 → [2] + 2

1+2+1, 1+1+1+1, 2+1+1, 3+1 → [3] + 1

[5] - 13개 (2+4+7)

1+1+3, 2+3 → [2] + 3

1+2+2, 1+1+1+2, 2+1, 3+2 → [3] + 2

1+3+1, 1+1+2+1, 2+2+1, 1+2+1+1, 1+1+1+1+1, 2+1+1+1, 3+1+1 → [4] + 1

위와 같이 시뮬레이션을 해보면 DP[N] = DP[N-3] + DP[N-2] + DP[N-1]의 점화식을 구할 수 있다.

// BOJ 9095 1, 2, 3 더하기
#include <iostream>
 
using namespace std;
 
int dp[12];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for (int i = 4; i <= 11; i++)
            dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
    int tc;
    cin >> tc;
    while (tc--) {
        int input;
        cin >> input;
        cout << dp[input] << '\n';
    }
    return 0;
}