[백준/C++] 24416 알고리즘 수업 - 피보나치 수1 (B1)

 

https://www.acmicpc.net/step/16

유형	난이도	완료일	특이사항
DP	브론즈4	23/02/05

 

<내 코드>

#include <iostream>

using namespace std;

int r_cnt=0;
int dc_cnt=0;
int arr[40];

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

int fibonacci(int n) 
{
    arr[1] = 1;
	arr[2] = 1;
    for(int i = 3; i <= n; i++)
	{
		arr[i] = arr[i-1] + arr[i-2];
		dc_cnt++;
	}
        
    return arr[n];
}

int main(void)
{
	int n;
	cin >> n;
	
	fib(n);
	fibonacci(n);
	
	cout << r_cnt<<" "<<dc_cnt;
}**

피보나치 수를 구하는 방식 중 재귀 함수를 이용한 방법과 동적 프로그래밍을 이용한 방법을 비교하는 문제다.

50번째 피보나치 수만 하더라도 재귀함수를 사용하면 832040번의 연산이 필요하지만 동적 계획법을 사용할 경우 28번만에 답을 구할 수 있었다.

가장 작은 n =1, n=2의 값을 미리 구해 저장해두고, 앞의 값을 이용해 뒤의 값들을 차례대로 구하는 것이다.

이 문제를 통해 가장 작은 부분의 결과를 이용해 답까지 구하는 DP 방식의 효율성을 알 수 있다.