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

problem

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

입력 : 테스트 케이스 T, T개의 n

출력 : 1, 2, 3을 통해 n을 만들 수 있는 경우의 수

 

solution

다이나믹 프로그래밍을 이용해서 푼다(dp[i] = 1, 2, 3 을 이용해 i 를 만들 수 있는 경우의수)

1. dp[1] = 1, dp[2] = 2, dp[3] = 4 (1 / 1+1, 2 / 1+1+1, 1+2, 2+1, 3)

2, dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

2. 3 ~ 11 까지  값을 dp에 저장한다.

 

code 

#include <iostream>
#include <vector>


using namespace std;

int main()
{
    int dp[11], t;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for(int i = 4; i < 11; i++){
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
    }

    cin >> t;
    while(t--){
        int n;
        cin >> n;
        cout << dp[n] << endl;

    }

}