BOJ 9507번 Generations of Tribbles

BOJ : https://www.acmicpc.net/problem/9507

github : https://github.com/junho0956/Algorithm/blob/master/9507/9507/%EC%86%8C%EC%8A%A4.cpp

 

문제에서 0 1 2 3 4 에 대한 dp 값이 주어져있기 때문에 조건문이 없어도

문제를 해결할 수 있습니다.

 

#include <iostream>
using namespace std;
typedef long long ll;
ll dp[68] = { 1,1,2,4,8, };
 
ll solve(int num) {
    
    ll& res = dp[num];
    if (res) return res;
 
    return res = solve(num - 1) + solve(num - 2) + solve(num - 3) + solve(num - 4);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    solve(67);
 
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        cout << dp[n] << "\n";
    }
 
    return 0;
}