백준 1003 - 피보나치 함수

본 문제의 요구사항은 다음과 같다

피보나치 수를 구하는 방법중의 하나로 재귀호출 방법을 이용할 수 있는데 기저조건 즉 재귀함수의 탈출조건이 반드시 있어야 한다. 입력되는 n 이 0 또는 1 인 경우 0 또는 1을 반환해야 한다. 이때 임의의 숫자  N 의 피보나치 수를 구하기 위해서는 0 또는 1 에 대한 피보나치수 함수 호출이 몇번 발생하는 지 계산해야 한다. 단 N 은 최대 40이다.

 

본 문제를 풀기위해서 피보나치 수를 구하는 함수와 동일하게 

 fibonacci(N) = fibonacci(N-1) + fibonacci(N-2)

라는 수식을 이용할 수있다.  예를 들어  10 에 대한 fibonacci(0) , fibonacci(1) 호출회수는

9에 대한 호출 회수 와 8 에 대한 호출회수 의 합으로 계산될수 있다.

 

간단하게 구현되는 코드는 다음과같다

 

pair<int, int> getResult(int n)
{
	if (n == 0) return make_pair(1, 0);
	if (n == 1) return make_pair(0, 1);

	auto r1 = getResult(n - 1);
	auto r2 = getResult(n - 2);
	return make_pair(r1.first + r2.first, r1.second + r2.second);
}

 

하지만 위와 같이 코드를 작성하여 문제를 제출해보면 시간 초과가 발생한다.

왜냐하면 문제를 풀이하는 과정에서 중복되는 계산이 빈번하게 발생하기 때문이다.

 

예를들어  getReuslt(10) 을 구한다고 생가해보고 다음과 같이 식을 계속 전개할 수있다.

getReuslt(10) = getReuslt(9) + getReuslt(8)

                  = getReuslt(8) + getReuslt(7) + getReuslt(7) + getReuslt(6)

계속 수식을 확장할수 있지만 1단계만 확장을 해도 getReuslt(7) 이 2번 발생한다. 만약 각 수에 대해서 getReuslt(n) 의 계산 결과를 별도로 저장한다면 계산의 회수를 단축할 수 있다.

 

최종 완성되는 코드는 아래와 같다.

 

#include <iostream>
#include <vector>

using namespace std;

pair<int, int> getResult(int n);

vector<int> gMemo0, gMemo1;

int main()
{
	gMemo0.resize(41, -1);
	gMemo1.resize(41, -1);

	int nrTC;
	scanf("%d", &nrTC);

	for (int i = 0; i < nrTC; i++)
	{
		int n;
		scanf("%d", &n);
		auto result = getResult(n);
		printf("%d %d\n", result.first, result.second);
	}
}

pair<int, int> getResult(int n)
{
	if (n == 0) return make_pair(1, 0);
	if (n == 1) return make_pair(0, 1);

	if (gMemo0[n] != -1)
		return make_pair(gMemo0[n], gMemo1[n]);

	auto r1 = getResult(n - 1);
	auto r2 = getResult(n - 2);
	gMemo0[n] = r1.first + r2.first;
	gMemo1[n] = r1.second + r2.second;
	return make_pair(r1.first + r2.first, r1.second + r2.second);
}

 

getResult 함수를 살펴보면 만약 이전에 계산된 값이 있으면 그 값을 리턴하고 그외의 경우 계산 결과 반환 전 결과를 메모하도록 구현되어있다. 메모제이션 기법을 이용한 동적 프로그래밍이다.

 

 

 

 

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

1003번: 피보나치 함수