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

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

1003번: 피보나치 함수

n의 0과 1의 호출 횟수를 pair형태로 반환하는 함수를 만들었다. n-1과 n-2의 0의 호출횟수합과, n-1과 n-2의 1의 호출횟수합을 통해 n의 0과 1의 호출 횟수를 구한다. cache[41]를 통해 이미 계산한 적이 있는 값은 한 번 더 계산하지 않도록해서 계산 시간을 단축시켰다.

 

코드

#include <iostream>
#include <utility>
using namespace std;

pair<int,int> cache[41];

//n의 0과 1의 호출횟수를 pair형태(0의 호출횟수, 1의 호출횟수)로 반환
pair<int,int> solve(int n)
{
	//기저사례
	if (n == 0)
	{
		return pair<int, int>(1, 0); //(0의 호출:1, 1의 호출:0)
	}
	else if (n == 1)
		return pair<int, int>(0, 1); //(0의 호출:0, 1의 호출:1)

	pair<int,int>& ret = cache[n];

	//이미 계산한적 있을때
	if (ret.first !=0 || ret.second != 0)
		return ret;

	//n-1과 n-2의 0의 호출횟수합과 1의 호출횟수합을 통해 n의 0과 1의 호출횟수를 구한다
	pair<int, int> n_1 = solve(n - 1);
	pair<int, int> n_2 = solve(n - 2);
	ret.first = n_1.first + n_2.first;
	ret.second = n_1.second + n_2.second;

	return ret;
}

void makeCache()
{
	//(0,0)으로 초기화 한다
	for (int i = 0; i < 41; i++)
	{
		cache[i].first = 0;
		cache[i].second = 0;
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int t, n;
	pair<int, int> result;

	//cache 초기화
	makeCache();

	cin >> t;

	for (int i = 0; i < t; i++)
	{
		cin >> n;
		result = solve(n);
		cout << result.first << " " << result.second << "\n";
	}

	return 0;
}