백준 1003번 C++

백준 1003번 피보나치 함수

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

1003번: 피보나치 함수

정답 코드

#include <iostream>
using namespace std;
int arr[41];
int fibonacci(int n)
{
	if (n == 0)
		arr[0] = 0;
	else if (n == 1)
		arr[1] = 1;
	else if (arr[n] == 0)
		arr[n] = fibonacci(n - 1) + fibonacci(n - 2);
	return arr[n];
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int num;
	cin >> num;
	fibonacci(40);

	int N;
	for (int x = 0; x < num; x++)
	{
		cin >> N;
		if (N == 0)
			cout << "1 0" << '\n';
		else
			cout << arr[N - 1] << " " << arr[N] << '\n';
	}
	return 0;
}

문제 풀이

전형적인 재귀 함수를 이용한 피보나치 함수 구현
문제입니다. 거기서 0과 1이 출력되는 횟수를 구하면
되는 문제인데 그냥 재귀로는 시간초과가 떠서 dp방식을 사용해서 피보나치 함수를 구현하였습니다.
n이 0일때, 1일때를 구분한 후 그 이상부터는 배열안에
값이 채워져 있지 않으면 배열 안에 피보나치 함수를 호출하여 값을 넣도록 하였습니다. 마지막으로 main함수 첫 부분에 ios_base::sync_with_stdio(false)와 cin.tie를 추가하였는데 이는 c++만의 독립적인 버퍼를 만들어줘서 실행시간이 줄어들게 됩니다. 그 후 cin과
cout의 묶음을 풀어줍니다. 이 두 문장은 c++문제를 풀 때 유용한 문장입니다.