[백준/BOJ] 2748번 피보나치 수 2 (C++)

www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

dp 유형의 문제입니다.

dp를 이용해서 피보나치 수를 구현하면 쉽게 풀 수 있는 문제인데, 이때 n의 최대값이 90이므로 int 범위가 벗어나므로, long long 타입을 사용하는 것을 주의합니다.

 

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;

ll dp[91];

ll F(int n) {
	if(dp[n] != -1) return dp[n];
	if(n == 0) return 0;
	if(n == 1) return 1;
	return dp[n] = F(n - 1) + F(n - 2);
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    memset(dp, -1, sizeof(dp));
    cout << F(n);
}