BOJ) 1003. 피보나치 함수 ( C / C++)

1. 문제 링크

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

2. 문제 개요

 피보나치 함수 재귀 호출에 의하여 (0)과 (1)이 몇 번 호출되는지 세는 프로그램 구현.

 

3. 문제 힌트!! ( 힌트만 보고 다시 구현해보세요. )

 dp배열을 만들 때 0과 1이 따로들어가도록 2개 선언하기.

 기존의 피보나치 함수는 값을 반환했는데(0에서 0, 1에서 1), 이번에는 0의 개수, 1의 개수를 반환하기. 

 

4. 문제 풀이

 피보나치 함수에서 반환 할 때 pair를 사용했습니다.

pair <int, int> dp[n]은 입력되는 수가 n일 때의 0과 1이 호출되는 횟수를 가지고 있도록 구현하였습니다.

n값이 증가되어 갈 때 정확한 수열의 값을 알 필요는 없습니다. 다만 n일 때 0과 1이 몇 번 호출되는지만 기억해나가면서 문제를 풀었습니다.

전체적인 틀은 기존의 피보나치 함수값 구하는 문제와 동일합니다.

 

 

5. 코드

#include <cstdio>
#include <algorithm>
using namespace std;

// pair<0, 1>. dp[n]으로 n에서 0과 1이 몇번 발생하는지
pair<int, int> dp[41];

pair<int,int> fibo(int n)
{
	//finish condition
	if (n == 0) return make_pair(1, 0);
	if (n == 1) return make_pair(0, 1);

	//memoization
	if (dp[n].first != 0 && dp[n].second != 0)	return dp[n];


	pair<int, int> left = fibo(n - 1);
	pair<int, int> right = fibo(n - 2);
	return dp[n] = make_pair(left.first + right.first, left.second + right.second);

}


int main(void)
{
	//초기값
	dp[0].first = 1;
	dp[1].second = 1;

	//40까지 그냥 계산
	fibo(40);

	int t;
	scanf("%d", &t);
	
	while (t--)
	{
		int n;
		scanf("%d", &n);

		printf("%d %d\n", dp[n].first, dp[n].second);
	}

	return 0;
}

 

 

 

 

지적, 댓글 언제나 환영입니다~