백준 10870번 c++ 풀이

안녕하세요 오늘은 다이나믹 프로그래밍을 이용한 문제를 풀겠습니다.

 

피보나치 수열은 워낙 유명해서 다들 아시죠? F(n) = F(n-1) + F(n-2)

이 문제를 두가지 방법으로 풀었습니다 

 

첫번째는 피보나치 함수를 만들어서 재귀로 호출해주는 방법입니다 코드는 다음과 같습니다.

#include <bits/stdc++.h>

using namespace std;

int fibonacci(int n){
    if(n==0) return 0;
    if(n==1) return 1;
    return fibonacci(n-1) + fibonacci(n-2);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int a;
    cin>>a;
    cout<<fibonacci(a);
    
}

메모리: 2020KB, 시간 0ms

 

두번째는 다이나믹 프로그래밍을 이용한 방법으로 입력값이 클때, 코드 실행 시간이 더 작은 코드입니다.

#include <bits/stdc++.h>
#include <vector>

using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	vector<int> v(25);

	int n;
	cin>>n;
	n++;
	v.at(1) = 0;
	v.at(2) = 1;
	if(n<=2){
		cout<<v.at(n);
	}
	else{
		for(int i = 3; i<=n; i++){
			v.at(i) = v.at(i-1) + v.at(i-2);
			
		}

		cout<<v.at(n);
	}
}

메모리: 2020KB, 시간: 0ms

 

두 코드의 메모리와 시간차이는 없습니다.

하지만 만약 n의 값이 무수히 커진다면 다이나믹 프로그래밍을 이용한 2번째 코드가 훨씬 빠를것입니다.