[백준] 1003번 : 피보나치 함수

 

 

문제 해결 구현:

#include <iostream>
using namespace std;

// arr[a][b]의 값은 a를 호출할때 b를 호출하게 되는 횟수
int arr[40][2];

void calculate()
{
	arr[0][0] =1;
	arr[1][1] = 1;
	for(int i=2; i<41; i++)
	{
		//fib(N) = fib(n-1) + fib(n-2)
		arr[i][0] = arr[i-1][0] + arr[i-2][0];
		arr[i][1] = arr[i-1][1] + arr[i-2][1];
	}
}

int main() {
	
	int t,n;
	calculate();
	
	cin >> t;
	for(int i=0; i<t; i++)
	{
		cin >> n;
		cout << arr[n][0] << ' ' << arr[n][1] << endl;
	}
	
	return 0;
}

 

 

 

arr[a][b] 는 a를 호출할때 b를 호출하게 되는 횟수를 의미하게 구현하여 배열을 보고 직관적으로 의미를 파악할 수 있게 하였다. 예를들어 arr[40][0] 이면 fibo(40)을 호출했을때 fib(0)이 몇번 호출됬는지가 저장되어 있는 것이다. 

 위 문제에서 최적 부분 구조는 fib(N)을 구하기 위해서 fib(N-1)과 fib(N-2)를 호출해야 한다는 부분이었다. 따라서 0과 1을 직접 저장해준 후 나머지는 for문을 돌려가며 저장해줄 수 있었다.