[백준] 9507번 Generations of Tribbles

[적용한 알고리즘]

DP

 

[아이디어]

재귀를 이용하는 dp의 기본형이다.  long long!

<코드>

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

long long dp[68];
long long Koong(int n){
    long long &ret = dp[n];

    if (n < 2) return 1;
    if (n == 2) return 2;
    if (n == 3) return 4;
    if (ret != -1) return ret;
    
    return ret = Koong(n - 1) + Koong(n - 2) + Koong(n - 3) + Koong(n - 4);
}

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

    while (t--){
        int N;
        scanf("%d", &N);
        memset(dp, -1, sizeof(dp));
        printf("%lld\n", Koong(N));
    }

    return 0;
}