백준 피보나치 수 2747

문제

특징

• 이것은 예전에 그냥 피보나치 함수를 넣어서 풀었던 문제이다. 그렇게 풀 수도 있지만 dp top-down방식으로도 가능하다

• 시간복잡도는 solve함수에서 2개의 재귀를 돌려서 2^n이다.

소스

#include <iostream>
#include <memory.h>


using namespace std;

//dp[i] i는 i번째 피보나치수의 값
//dp[n] =do[n-1] + dp[n-2] 

int n;
int dp[200];

//시간복잡도 2^n 
int solve(int idx) {

    if (idx < 1) return 0;

    if (dp[idx] != -1) return dp[idx];

    dp[idx] = solve(idx - 1) + solve(idx - 2);

    return dp[idx];

}

int main() {

    cin >> n;

    memset(dp, -1, sizeof(dp));

    dp[1] = 1;
    dp[2] = 1;

    cout << solve(n);
    return 0;
}