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

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

1003번: 피보나치 함수

문제

풀이

아~~ 주 쉽게 생각했다가 짜증만 엄청 냈던 문제..

시간초과를 생각못하고 어떻게 풀던 시간초과가 나오고, 계속 '이렇게해서 안되면 어쩌란거야 ?'를

반복하다가 찾아보니 점화식을 이용하는 문제였다. 

 

이럴거면 피보나치 위에 그 함수코드는 왜있었는지 이해불가..

 

아무튼 피보나치 함수의 점화식은 아래와 같다.

 

N이 0일때, return값이 0인경우 = 1, 1인경우 = 0

N이 1일때, return값이 0인경우 = 0, 1인경우 = 1

N이 2일때, return값이 0인경우 = 1, 1인경우 = 1

N이 3일때, return값이 0인경우 = 1, 1인경우 = 2

N이 4일때, return값이 0인경우 = 2, 1인경우 = 3

N이 5일때, return값이 0인경우 = 3, 1인경우 = 5

.....

 

0[N] = 0[N-1] + 0[N-2]

1[N] = 1[N-1] + 1[N-2] 

 

와 같다고 볼 수 있다.

그럼 문제는 아주 간단해진다. 아래 코드를 참조하자

 

Code ( C++ )

#include <iostream>

using namespace std;

int T, N;
int _zero[41] = { 1,0, };
int _one[41] = { 0,1, };

int main()
{
	cin >> T;

	while (T--)
	{
		cin >> N;

		for (int i = 2; i <= N; i++)
		{
			_zero[i] = _zero[i - 1] + _zero[i - 2];
			_one[i]  = _one[i - 1] + _one[i - 2];
		}
		cout << _zero[N] << " " << _one[N] << "\n";
	}
}