BOJ 2748 피보나치수 2

2748번: 피보나치 수 2

-문제 

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 

-입력

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

문제풀이

기본적인 피보나치수 문제중 하나입니다. 여기서 중요한 점 부분은 "n은 90보다 작거나 같은 자연수이다." ==>( n이 90까지면 피보나치 수는 엄청 커집니다.)

물론 DP를 사용하여 문제를 풀수도 있지만 현재 저는 재귀를 사용하여 문제를 풀고 있기 때문에 재귀함수를 사용해서 문제를 풀고 있습니다. 

맨 처음에 일반적인 재귀함수를 사용한 피보나치 수를 구하는 방법으로 시도하였지만 시간 초과로 인하여 계속 오답이 나왔습니다. 

문제점을 찾아보니 일반적인 재귀함수를 사용한 피보나치 수를 구하는 방법으로 시도한다면 피보나치 수를 계산할 때 마다 계속 이전에 계산하였던 값을 중복으로 계산하기 때문에 시간초과가 떠 오답으로 처리가 되었습니다. 

따라서 이 문제를 풀 때 사용한 방법은 피보나치 수를 저장할 배열을 선언 후 -1로 초기화를 해놓고 이전에 계산하지 않은 피보나치 수만 배열에 갱신하여 값을 구하도록 했습니다. 
따라서 일반 적인 방법으로 피보나치 수를 구하면 시간 복잡도는 O(2^N)이고 최종적인 방법으로 계산한다면 O(N)입니다

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
long long memo[91];
long long int fibo(int a)
{
	if (a == 0)
	{
		memo[a] = 0;
	}
	else if (a == 1)
	{
		memo[a] = 1;
	}
	else if (memo[a] == -1)
		//==> 피보나치 수를 계속 재귀 돌면서 구하는것이
		//  아닌 계산하지 않은 수만 계산하도록 함
		memo[a] = fibo(a - 1) + fibo(a - 2);
	return memo[a];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	fill(memo, memo + 91, -1);
	int count;
	cin >> count;
	cout << fibo(count);
}

 

글 내용 중에 틀린 것이 있거나 궁금한 것이 있다면 댓글 남겨주세요! 봐주셔서 감사합니다!