백준[1003 번] - 피보나치 함수

문제

분석

주의할 것이 시간제한이 0.25초이다.

즉, 문제에서 주어진 함수를 이용하게 되면 시간 초과가 뜨게 된다.

이 문제를 풀기 위해서는 메모이제이션을 이용해서 풀어야 한다.

"피보나치 수 2"에서 구현한 소스를 재사용해서 구현해봤다.

 

구현

#define MAX 50
using namespace std;

class cnt
{
public:
	int cnt_0;
	int cnt_1;
	
	cnt operator+(const cnt& other)
	{
		cnt ret;
		ret.cnt_0 = this->cnt_0 + other.cnt_0;
		ret.cnt_1 = this->cnt_1 + other.cnt_1;
		return ret;
	}
};


cnt cnt_cache[MAX];
cnt fibo(int n)
{
	cnt& ret = cnt_cache[n];
	//base case
	if (n == 1)
	{
		ret.cnt_1 = 1;
		return ret;
	}
	if (n == 0)
	{
		ret.cnt_0 = 1;
		return ret;
	}
	//계산한적이 있는 경우
	if (ret.cnt_0 + ret.cnt_1 != 0)
	{
		return ret;
	}
	return ret = fibo(n - 1) + fibo(n - 2);
}

int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		memset(cnt_cache, 0, sizeof(cnt_cache));
		int n;
		cin >> n;
		cnt ans = fibo(n);
		cout << ans.cnt_0 << ' ' << ans.cnt_1 << '\n';
	}
	return 0;
}

 

회고

카운트하는 부분을 struct이나 pair로도 구현할 수 있다.

이 방법을 이용하면 시간 복잡도가 O(n) 이 나온다.