15989 1, 2, 3더하기 4

와.. 어떻게 풀지 감도 안 잡히는 문제였다.

 

고민하다가 못풀겠다 싶어서 다른 풀이들을 봤다.

 

dp 문제였구나

 

 

dp문제는 어떻게 풀어야할지 고민하는 능력을 좀 길러야겠다..

 

다음부터는 dp라는 거 인지하면 식을 세워봐야겠음

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int dp[10005][3];

int     main()
{
    int t;
    scanf("%d", &t);

    dp[1][0] = 1;
    dp[2][0] = 1;
    dp[2][1] = 1;
    dp[3][0] = 1;
    dp[3][1] = 1;
    dp[3][2] = 1;

    for (int i = 4; i < 10005; i++)
    {
        dp[i][0] = 1;
        dp[i][1] = dp[i - 2][1] + dp[i - 2][0];
        dp[i][2] = dp[i - 3][2] + dp[i - 3][1] + dp[i - 3][0];
    }

    for (int i = 0; i < t; i++)
    {
        int n;
        scanf("%d", &n);

        printf("%d\n", dp[n][0] + dp[n][1] + dp[n][2]);
    }

    return 0;
}