피보나치 함수 (백준 - 1003번)

역시 동적계획법을 사용하여 푸는 문제이다.

 

우선 규칙을 살펴보자. 피보나치 규칙인 F(N) = F(N - 1) + F(N - 2)를 염두해두고 보자.

 

* N이 0일때

0 호출 횟수 = 1

1 호출 횟수 = 0

 

* N이 1일때

0 호출 횟수 = 0

1 호출 횟수 = 1

 

* N이 2일때

0 호출 횟수 = (1일때 0 호출 횟수) + (0일때 0 호출 횟수) = 0 + 1 = 1

1 호출 횟수 = (1일때 1 호출 횟수) + (0일때 1 호출 횟수) = 1 + 0 = 1

 

* N이 3일때

0 호출 횟수 = (2일때 0 호출 횟수) + (1일때 0 호출 횟수) = 1 + 0 = 1

1 호출 횟수 = (2일때 1 호출 횟수) + (1일때 1 호출 횟수) = 1 + 1 = 2

 

0과 1의 호출 횟수가 필요하기 때문에 둘을 분리하여 관리 할 수 있도록 구조체를 사용하여 연산을 진행하면 편하다. 하지만 나는 편하게 구조체를 초기화 하고 연산자 =과 +를 구조체에서도 사용 할 수 있도록 operator를 사용하였기 때문에 구조체를 class로 정의하였다.

 

코드는 다음과 같다.

#include <iostream>
using namespace std;

class DATA
{
public:
	int call_zero = 0;
	int call_one = 0;

	DATA operator+(DATA& other)
	{
		DATA temp;
		temp.call_zero = call_zero + other.call_zero;
		temp.call_one = call_one + other.call_one;
		return temp;
	}
	void operator=(DATA other)
	{
		call_zero = other.call_zero;
		call_one = other.call_one;
	}
};

int main()
{
	DATA dp[40 + 1];
	dp[0].call_zero = 1;
	dp[1].call_one = 1;

	for (int i = 2; i <= 40; ++i)
	{
		dp[i] = dp[i - 1] + dp[i - 2];
	}

	int input;
	cin >> input;

	int* list = new int[input];
	for (int i = 0; i < input; ++i)
	{
		cin >> list[i];
	}

	for (int i = 0; i < input; ++i)
	{
		DATA& d = dp[list[i]];
		cout << d.call_zero << " " << d.call_one << endl;
	}
	delete[] list;
}