백준 2748번 c++ 풀이

안녕하세요 오늘은 동적계획법을 이용한 피보나치 수열 문제를 풀어보겠습니다.

 

전략:

1. long long int타입으로 v라는 array를 생성해줍니다. 

2. long long int타입으로 return하는 fibo라는 함수를 선언해주고, 0이면 0을, 1이면 1을 반환해줍니다.

3. 만약 v[n]이 비어있다면 v[n]은 fibo(n-1) + fibo(n-2)로 넣어주고, 차있다면 v[n]을 반환해줍니다.

 

코드:

#include <bits/stdc++.h>
using namespace std;
long long int v[100];
long long int fibo(int n){
	if(n==0){
		return 0;
	}
	else if(n==1){
		return 1;
	}
	if(!v[n]){
		v[n] = fibo(n-1) + fibo(n-2);
		return v[n];
	}
	else {
		return v[n];
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 	v[0] = 0;
	v[1] = 1;
	int N;
	cin>>N;
	cout<<fibo(N)<<"\n";
}