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

백준의 Generation of Tribbles(9507) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 사실 이 문제를 풀 때, 뭘 구현해야되는 문제인지 잘 몰랐었다... 문제에 답이 주어져있어서 혹여나 재귀를 DP로 바꿔봤는데

   맞았습니다를 받았다...

   문제에서 주어진 재귀 방식을 DP로 바꾸기만 하면 끝 !

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
typedef long long ll;
#define endl "\n"
#define MAX 68
using namespace std;
 
int N;
ll DP[MAX];
 
void Initialize()
{
    memset(DP, 0, sizeof(DP));
}
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    DP[0] = 1;
    DP[1] = 1;
    DP[2] = 2;
    DP[3] = 4;
 
    for (int i = 4; i <= N; i++)
    {
        DP[i] = DP[i - 1] + DP[i - 2] + DP[i - 3] + DP[i - 4];
    }
    cout << DP[N] << endl;
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}