[백준 문제풀이 / 동적계획법 1] 24416. 알고리즘 수업 - 피보나치 수 1

문제 내용

 

피보나치 수열문제를 재귀로 풀었을 때, 동적프로그래밍으로 풀었을 때 실행 횟수의 차이를 구하는 문제.

 

문제 풀이

사실 풀이는 없다. 수도 코드를 C++ 스타일로 바꿔서 실행횟수를 출력해주기만 하면 된다.

하지만 올리는 이유는 피보나치 함수의 재귀와 동적 프로그래밍의 어떻게 동작 하는지 차이를 직관적으로 볼 수 있기 때문이다.

 

#include <iostream>
using namespace std;

int f[41];
int playCnt1 = 1;
int playCnt2 = 0;

int fib(int n)
{

	if (n == 1 || n == 2)
	{
		return 1;  //# 코드1
	}
	else
	{
		playCnt1++;
		return (fib(n - 1) + fib(n - 2));
	}
	
}

int fibonacci(int n) 
{
	f[1] = f[2] = 1;

	for (int i = 2; i < n; i++)
	{
		playCnt2++;
		f[i] = f[i - 1] + f[i - 2];  //# 코드2
	}
	
	return f[n];
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);


	int n;
	cin >> n;

	fib(n);
	fibonacci(n);


	cout << playCnt1 << endl;
	cout << playCnt2 << endl;
}