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

 

 

풀이과정

---

Dynamic Programming을 사용한다.

 

점화식을 구하면

1.f(0)일 때 0은 1, 1은 0번 출력된다. 

 

2.f(1)일 때 0은 0, 1은 1번 출력된다. 

 

3. n이 2보다 클 때 f(n)일 때,

0은 f(n-1)의 0 출력 횟수, f(n-2)의 0 출력 횟수   번 출력 된다. 

1은 f(n-1)의 1 출력 횟수, f(n-2)의 1 출력 횟수

즉, f(n) = f(n-1) + f(n-2)

 

0과 1의 출력 횟수를 나타내는 pair<int,int>형 배열 d[41](n이 40보다 작거나 같다) 에

점화식에 맞게 0과 1의 출력 횟수를 대입해준다.

 

코드

---

#include <iostream>
using namespace std;

int main()
{
	pair<int, int> d[41] = { { 1,0 } ,{ 0, 1 } , };
	int iInput = 0;

	for (int i = 2; i < 41; ++i)
	{
		d[i].first = d[i - 1].first + d[i - 2].first;
		d[i].second = d[i - 1].second + d[i - 2].second;
	}

	cin >> iInput;
	for (int i = 0; i < iInput; ++i)
	{
		int n;
		cin >> n;
		cout << d[n].first << " " << d[n].second << endl;
	}
	return 0;
}