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

1003 피보나치 함수

#include <bits/stdc++.h>
using namespace std;

int fibo(int num);
int check_zero = 0, check_one=0;
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int test_case;
	cin >> test_case;
	for (int i = 0; i < test_case; ++i)
	{
		int tmp;
		cin >> tmp;
		fibo(tmp);
		cout << check_zero << " " << check_one << "\\n";
		check_one = 0;
		check_zero = 0;
	}
	return 0;
}

int fibo(int num)
{
	if (num <= 0)
	{
		if (num == 0)
			++check_zero;
		return 0;
	}
	else if (num == 1)
	{
		++check_one;
		return 1;
	}
		
	return fibo(num - 2) + fibo(num - 1);
}

• 이 코드의 경우 시간초과가 나서 실패했다.
• 찾아보니 dp 테이블을 이용해서 문제를 풀어야 했다.
• 1,2,3 피보나치를 구했을 때, 수열이 증가하는것을 봐서 찾아야한다.

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int test_case;
	cin >> test_case;
	vector<int> dp_table = { 0,1,1 };
	for (int i = 3; i < 41; ++i)
	{
		dp_table.push_back(dp_table[i - 2] + dp_table[i - 1]);
	}
	for (int i = 0; i < test_case; ++i)
	{
		int tmp;
		cin >> tmp;
		if (0 == tmp)
			cout << 1 << " " << 0 << '\\n';
		else if (1 == tmp)
			cout << 0 << " " << 1 << '\\n';
		else
			cout << dp_table[tmp - 1] << " " << dp_table[tmp] << '\\n';
	}
	return 0;
}

• vector가 아니라 그냥 배열을 할당해두고 하면 조금 더 편한 것 같다.