백준 1003번: 피보나치 함수

[문제 링크]

1003번: 피보나치 함수

---

간단한 DP 문제였다. 0과 1이 호출되는 횟수를 카운팅하기 위해 pair 컨테이너를 사용하였고,

pair 컨테이너의 first 에는 0이 호출되는 횟수, second 에는 1이 호출되는 횟수를 저장하는 형태로 구현하였다.

 

끝으로 피보나치 함수의 점화식이 Sol(n) = Sol(n-1) + Sol(n+1) 인 것을 활용하면 원하는 결과를 얻을 수 있다.

---

#include <iostream>
using namespace std;

pair<int, int> memo[41];

pair<int, int> Solution(int n)
{
	if (n == 0 || n == 1) return memo[n];

	pair<int, int>& ret = memo[n];
	if (ret.first != -1 && ret.second != -1) return ret;

	pair<int, int> a, b;
	a = Solution(n - 1);
	b = Solution(n - 2);

	return ret = make_pair(a.first + b.first, a.second + b.second);
}

int main(void)
{
	for (int i = 2; i < 41; i++)
		memo[i] = make_pair(-1, -1);

	memo[0] = make_pair(1, 0);
	memo[1] = make_pair(0, 1);

	int tc;
	cin >> tc;
	while (tc--)
	{
		int n;
		cin >> n;
		pair<int, int> res = Solution(n);
		cout << res.first << ' ' << res.second << endl;
	}
	
	return 0;
}

알고리즘 200일 프로젝트 - 63 day