[#1003] 피보나치 함수

#include <iostream>
#include <vector>
 
using namespace std;
 
vector<long long> cache(91, -1);
 
long long fibo(int n) {
    if (n <= 1) {
        cache[n] = n;
        return n;
    }
    
    long long& ret = cache[n];
 
    if (ret != -1) {
        return ret;
    }
 
    return ret = fibo(n - 2) + fibo(n - 1);
}
 
int main() {
    int t;
    cin >> t;
    for (int tc = 0; tc < t; tc++) {
        int n;
        cin >> n;
 
        fibo(n);
 
        if (n == 0) {
            cout << "1 0\n";
        }
        else if (n == 1) {
            cout << "0 1\n";
        }
        else {
            cout << cache[n - 1] << " " << cache[n] << "\n";
        }
    }
    return 0;
}
 

피보나치 수2 할때 한 코드에서 고침

 

피보나치수를 구할때 fibo(1)과 fibo(0) 호출 횟수에는 규칙이 있음

fibo(0)의 호출 횟수 == fibo(n-1)

fibo(1)의 호출 횟수 == fibo(1)