[ DP - 1003 ] 피보나치 함수

 

---

접근법

 

처음엔 피보나치 함수의 Code가 주어졌으니, 직접 재귀함수를 실행하면서 n이 1 또는 0일 때, 조건문을 걸어 개수를 계산하려고 하였으나 역시나..시간초과!

따라서 DP문제이기에 몇가지를 시도해본 결과

 

 

왼쪽이 0이 출력되는 개수, 오른쪽이 1이 출력되는 개수이다. 즉 피보나치 함수의 재귀적인 호출 처럼 각각의 출력 개수 역시 -1, -2 번째의 출력 개수의 합으로 유도할 수 있음을 알 수 있다.

하지만 0의 경우 1,2번재 부터 유효하고, 1의 경우 0,1 부터 유효하므로 두 DP 배열의 0,1,2번째 원소는 직접 입력하고, 나머지는 반복문을 돌면서 계산하면 된다.

---

정답

#include<iostream>
#include<vector>
using namespace std;

int32_t st_DP0[41];
int32_t st_DP1[41];
vector<pair<int32_t, int32_t>> st_Result;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int32_t s32_T, s32_I;

	st_DP0[0] = 1;
	st_DP0[1] = 0;
	st_DP0[2] = 1;

	st_DP1[0] = 0;
	st_DP1[1] = 1;
	st_DP1[2] = 1;

	cin >> s32_T;
	for (s32_I = 3; s32_I <= 40; s32_I++)
	{
		st_DP0[s32_I] = st_DP0[s32_I - 1] + st_DP0[s32_I - 2];
		st_DP1[s32_I] = st_DP1[s32_I - 1] + st_DP1[s32_I - 2];
	}

	for (s32_I = 0; s32_I < s32_T; s32_I++)
	{
		int32_t s32_Tmp;
		cin >> s32_Tmp;
		st_Result.push_back(make_pair(st_DP0[s32_Tmp], st_DP1[s32_Tmp]));
	}

	for (s32_I = 0; s32_I < s32_T; s32_I++)
	{
		cout << st_Result[s32_I].first << " " << st_Result[s32_I].second << "\n";
	}

	return 0;
}

 

지금와서 보니 어짜피 0의 개수와 1의 개수는 인덱스 차이만 있을 뿐 동일한 결과이므로 하나의 배열로 관리해도 된다.