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

알고리즘 분류: 다이내믹 프로그래밍

문제 링크: https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

 

【 풀이 】

 

동적 계획법(DP, Dynamic Programming)을 이용하여 해결하는 문제이다.

동적 계획법은 한 문제를 여러 문제로 나누어서 각 문제는 단 한 번만 풀도록 각 답안을 매번 저장하는 알고리즘이다.

쉽게 말해서, 이 문제의 경우 피보나치 함수 호출 중에 이전에 호출했던 피보나치 수들은 다시 호출하지 않도록 따로 다른 테이블에 저장해 놓고 가져다 쓰는 것이다.

또한 이 문제는 0이 출력되는 횟수와 1이 출력되는 횟수의 규칙성을 찾는 것이 중요하다.

0부터 시작해서 n번째 숫자의 0이나 1이 출력되는 횟수는 다음과 같다.

 

• 0이 출력되는 경우: 1, 0, 1, 1, 2, 3, 5, 8...
• 1이 출력되는 경우: 0, 1, 1, 2, 3, 5, 8, 13...

 

즉 0의 횟수는 2번째 수부터 피보나치 수열이고, 1의 횟수는 처음부터 피보나치 수열이다.

 

 

 

【 코드 】

 

#include<iostream>
using namespace std;

pair<int,int>cnt[100];
int fibonacci0(int n)
{
	if (n == 0)
		return 1;
	else if (n == 1)
		return 0;
	else if (n == 2)
		return 1;
	else if (cnt[n].first != 0)
		return cnt[n].first;
	return cnt[n].first = fibonacci0(n - 1) + fibonacci0(n - 2);
}
int fibonacci1(int n)
{
	if (n == 0)
		return 0;
	else if (n == 1)
		return 1;
	else if (cnt[n].second != 0)
		return cnt[n].second;
	return cnt[n].second=fibonacci1(n - 1) + fibonacci1(n - 2);
}

int main(void)
{
	int t, n;
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		cin >> n;
		cout <<fibonacci0(n)<<' '<< fibonacci1(n) << '\n';
	}
	return 0;
}