BAEKJOON 1003 - 파보나치 함수

문제: https://www.acmicpc.net/problem/1003

파보나치를 구할 수 있는 재귀함수에서 0 과 1인 경우가 불리는 횟수는 나열을 해보면

0의 경우 주어진 n - 1 의 파보나치 수

1의 경우 주어진 n 의 파보나치 수와 같다는 것을 알 수 있습니다.

그리고 파보나치 수의 경우 n이 커지면 시간복잡도가 매우 커지기 때문에 memoization 을 사용해 시간 복잡도를 줄여 풀었습니다.

my solving

c++

#include <fstream>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
 
map<int, int> cache;
int fibonacci_dp(int num)
{
    map<int, int>::iterator it = cache.find(num);
    if (it != cache.end())
        return it->second;
 
    int ret = 0;
    if (num == 0)
        ret = 0;
    else if (num == 1)
        ret = 1;
    else
        ret = fibonacci_dp(num - 1) + fibonacci_dp(num - 2);
 
    cache.insert(make_pair(num, ret));
 
    return ret;
}
 
int main()
{
    int cases;
    cin >> cases;
    for (int i = 0; i < cases; i++)
    {
        int n;
        cin >> n;
        if (n == 0)
            cout << "1 0" << endl;
        else
            cout << fibonacci_dp(n - 1) << " " << fibonacci_dp(n) << endl;
    }
    return 0;
}