백준 10870번. 피보나치 수 5(c++) / dp

피보나치는 dp 알고리즘을 사용해서 풀 수 있는 전형적인 문제 중 하나이다.

피보나치 공식인 f(n) = f(n-1)+f(n-2) 를 사용해서 구현했다.

 

 

코드 첨부

// 피보나치 수 5
#include <iostream>
#include <cstring>
 
using namespace std;
 
int n;
int dp[22] = {0, };
 
int go(int N)
{
    if(dp[N]!=-1){
        return dp[N];
    }
    
    dp[N] = go(N-1)+go(N-2);
    return dp[N];
}
 
int main()
{
    memset(dp, -1, sizeof(dp));
    cin>>n;
    dp[0] = 0;
    dp[1] = 1;
    if(n>=2){
        dp[n] = go(n-1)+go(n-2);
    }
    
    cout<<dp[n]<<"\n";
}

 

문제 첨부

https://www.acmicpc.net/problem/10870

10870번: 피보나치 수 5