algorithm/Dynamic Programming
[C++] BOJ 2748
gartenhh
2021. 3. 27. 13:37
2748번: 피보나치 수 2
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가
www.acmicpc.net
코드
#include <iostream>
#include <string>
using namespace std;
long long fib[100], n; //fib[n]에 n번째 피보나치 수 저장
long long fibo(int n){
if(fib[n] != -1)
return fib[n]; //fib[n]이 구해졌다면 return fib[n]
if(n < 2)
return fib[n] = n; //n이 2보다 작을 때 fib[n]에 n값을 저장하고 return
return fib[n] = fibo(n - 1) + fibo(n - 2);
}
int main(){
for(int i=0;i<100;i++)
fib[i]= -1; //initialized to -1
cin >> n;
cout << fibo(n);
}풀이방법
DP중에 Top-down 이용