[백준] 9507 Generations of Tribbles

9507번: Generations of Tribbles

 

www.acmicpc.net

풀이

일반적인 피보나치 수열 문제를 풀 듯이 동적 계획법을 사용하면 쉽게 해결할 수 있다. 이 때 최대값이 int 범위를 벗어나기 때문에 long long으로 선언해야 해결할 수 있다.

코드

#include <iostream>
#include <vector>
using namespace std;

vector<long long> fib;

long long fibonacci(int n) {
    long long& ret = fib[n];
    if (ret != -1) return ret;
    if (n < 2) return ret = 1;
    if (n == 2) return ret = 2;
    if (n == 3) return ret = 4;
    else return ret = fibonacci(n - 1) + fibonacci(n - 2) + fibonacci(n - 3) + fibonacci(n - 4);
}

int main() {
    int t;
    cin >> t;
    fib = vector<long long>(68, -1);
    while (t--) {
        int n;
        cin >> n;
        cout << fibonacci(n) << '\n';
    }
    return 0;
}