[백준/BOJ] 1003 - 피보나치 함수(c++) (DP)

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

 

피보나치 함수는 대표적인 다이나믹프로그래밍 문제이다.

 

피보나치 함수는

 

f(0) = 0,

f(1) = 1,

n>=2, f(n) = f(n-1) + f(n-2)의 꼴이다.

 

위의 문제는 0이 나오는 횟수와 1이 나오는 횟수를 출력하는 것이다.

 

따라서 

 

n=0: {1,0}

n=1: {0,1}

n=2: {1,1}

n=3: {1,2}

n=4: {2,3}

....

 

이렇게 이어진다. 위의 순서를 보고 규칙을 찾으면

 

n=i: {i-1 의 첫번째 원소 + i-2 의 첫번째 원소, i-1 의 두번째 원소 + i-2 의 두번째 원소}이다.

 

따라서 이에 맞게 함수를 작성하면

 

pair<int,int> fibo(int a) {
	if (dp[a] != make_pair(0, 0)) return dp[a];
	pair<int,int> fa1 = fibo(a - 1), fa2 = fibo(a - 2);
	return dp[a] = make_pair(fa1.first + fa2.first, fa1.second + fa2.second);
}

라고 할수있다.

---

소스코드

#include <iostream>
#define pii pair<int,int>

using namespace std;

int T, a;
pii dp[41];

pii fibo(int a) {
	if (dp[a] != make_pair(0, 0)) return dp[a];
	pii fa1 = fibo(a - 1), fa2 = fibo(a - 2);
	return dp[a] = make_pair(fa1.first + fa2.first, fa1.second + fa2.second);
}

int main() {
	dp[0] = { 1,0 }, dp[1] = { 0,1 };
	cin >> T;
	while (T--) {
		cin >> a;
		pii ans = fibo(a);
		cout << ans.first << ' ' << ans.second << '\n';
	}
}