백준 11399번 "피보나치 함수" [Dynamic Programming 점화식]

 

 

문제

 

 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

문제 접근 순서.

 

1. 해당 문제는 시간제한이 0.25초로 빡빡한 문제로 일반적인 DFS 구조를 사용해서 재귀함수를 호출 하면서 O(2^n)씩 해당되므로

    c++ 1초당 계산이 약 10^8인 것을 계산하면 해당 방법으로는 문제를 해결할 수 없음을 알 수 있다.

 

2. DP 방법을 이용하는데 DP는 이전에 구한 값을 미리 저장해 두고 재사용하여 불필요한 함수 호출과 중복 계산을 제거하는 방식이다.

 

 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

#include <iostream>
#include <vector>

using namespace std; 


int main()
{

	int i_TestCaseCount; 

	cin >> i_TestCaseCount; 

	vector<pair<int, int>> m_vec;
	


	int dp_0[41] = { 0 };
	int dp_1[41] = { 0 };

	// 0 -> 1, 0
	// 1 -> 0 ,1
	// 2 -> 1 ,1
	// 3 -> 1 ,2  ( 1+2)
	// 4 -> 2, 3  ( 2+3)
	// 5 -> 3, 5  ( 4+3) 
	// 6 -> 5, 8  

	dp_0[0] = 1;
	dp_1[0] = 0;

	dp_0[1] = 0;
	dp_1[1] = 1;

	dp_0[2] = 1;
	dp_1[2] = 1;


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


	for(int i=0; i<i_TestCaseCount; i++)
	{
		int inputNum; 
		cin >> inputNum;
		
		m_vec.push_back(make_pair(dp_0[inputNum], dp_1[inputNum]));
	}

	for(auto& iter : m_vec)
	{
		cout << iter.first << " " << iter.second << "\n";
	}





	return 0;
}