[백준 9507] Generations of Tribbles (DP) (C/C++)

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
int T, N;
long long dp[70];
 
long long solve(int n)
{
    if(dp[n] != 0)
    {
        return dp[n];
    }
    
    for(int i = n-1; i >= n-4; i--)
    {
        dp[n] += solve(i);    
    }
    
    return dp[n];
}
 
int main(void)
{
//    freopen("B9507_input.txt", "r", stdin);
 
    cin >> T;
    
    dp[0] = 1, dp[1] = 1, dp[2] = 2, dp[3] = 4;
    
    while(T--)
    {
        cin >> N;
        
        cout << solve(N) << endl;    
    }
    
    return 0;
}