[DP] 백준 2748번 - 피보나치 수 2

 

case1) n이 0 혹은 1일 때, 

0 / 1을 출력

 

case2) n이 2이상 일 때,

memoizate해 놓은 이전 두개의 수를 더한 수를 출력

 

하지만 이런식으로 진행한다면 시간초과가 발생한다

 

 

memoization을 사용하여 연산을 최대한 줄여야 한다

 

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
using namespace std;
#define endl '\n'

int N;
long long fib[100];

long long pibo(int n)
{
    if(n==0){
        return 0;
    }
    if(n==1){
        return 1;
    }
    if(fib[n]!=-1)
        return fib[n];
    else{
        fib[n] = pibo(n-1)+pibo(n-2);
        return fib[n];
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    for(int i=0; i<100; i++){
        fib[i]=-1;
    }
    cin >> N;

    cout<<pibo(N)<<endl; 
}