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

문제링크 : https://www.acmicpc.net/problem/9507

9507번: Generations of Tribbles

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

ll dp[67];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int T;
    cin >> T;

    dp[0] = dp[1] = 1; //초기값들
    dp[2] = 2;
    dp[3] = 4;

    for(int i=4; i<=67; i++)
    {
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3] + dp[i-4]; //점화식
    }

    while(T--)
    {
        int n;
        cin >> n;
        cout << dp[n] <<"\n";
    }

    return 0;
}

크게 설명할 것이 없는 DP 문제이다.

모든 내용이 문제에 직관적으로 적혀있다.

여기서 주의할 것은 dp 배열에 int 값을 초과하는 값이 들어가므로 long long으로 선언해줘야 한다.