백준 2748 피보나치수2 c++ // 탑다운 dp 형식

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

2748번: 피보나치 수 2

 

#include <bits/stdc++.h>
using namespace std;
long long dp[91], n;
long long fibo(long long idx) {
    //기저사례
    if (idx == 0 || idx == 1) return idx;

    //메모
    long long& ret = dp[idx];
    if (ret) return ret; //값이 있으면 바로리턴

    //로직
    return ret = fibo(idx - 1) + fibo(idx - 2);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    cout << fibo(n) << '\n';
    return 0;
}