[백준 24416/c++]피보나치 수 1

어제랑 다른 버전의 피보나치 수 문제이다

재귀와 다이나믹 프로그래밍의 차이를 알 수 있는 문제였다

재귀는 반드시 함수를 만들어서 풀어야 하며, 매번 연산을 하면 너무 느리므로

top-down 방식의 memoization 을 사용하여 연산 속도를 향상 시킬 수 있다 (memoization이 필수는 아님)

다이나믹 프로그래밍의 경우 반드시 함수를 만들 필요는 없고 배열과 반복문만으로 만들 수 있으며

bottom-up 방식의 tabulation 을 사용한다 (tabulation이 필수임)

일반적으로 다이나믹 프로그래밍이 재귀함수를 사용한것보다 시간복잡도, 공간복잡도가 낮아서 성능이 좋다

https://www.acmicpc.net/problem/24416

24416번: 알고리즘 수업 - 피보나치 수 1

#include <bits/stdc++.h>
using namespace std;

int recur_cnt = 0;
int dynamic_cnt = 0;
int ar[44] = {0,};

int fib(int a)
{
	if (a == 1 || a == 2)
	{
		recur_cnt++;
		return 1;
	}
	else
	{
		return fib(a - 1) + fib(a - 2);
	}
}

void fibonacci(int b)
{
	ar[1] = 1;
	ar[2] = 1;
	for (int i = 3; i <= b; i++)
	{
		dynamic_cnt++;
		ar[i] = ar[i - 1] + ar[i - 2];
	}
}

int main(){
	
	long long answer;
	int n;
	
	cin >> n;
	
	fib(n);
	fibonacci(n);
	
	cout << recur_cnt << " " << dynamic_cnt << "\n";
	
	return 0;
}