[C++]BOJ 1003 - 피보나치 함수

시간 제한이 0.25초로 걸려있는 것이 정직하게 피보나치 돌리면 시간 초과가 뜬다는 것을 암시한 것인가.

n번째 피보나치를 구한다 생각하고 트리를 그려보면 매우 쉬워진다.
예를 들어 n번째 피보나치 수열을 구하는 트리에서 n + 1번째 피보나치 수열을 구하는 트리를 그린다 가정하면, 기존의 n이 부모인 트리에서 n + 1을 부모 노드로 추가하고 n - 1의 부분 트리가 하나 더 생긴다.
이것을 n + 1을 n으로 치환해서 읽어보면 n의 부모 노드에 n - 1과 n - 2의 자식 노드가 연결된 형태이다.
이 생각을 중심으로 0과 1 각각 갯수를 세어주면 된다.

#include <iostream>
using namespace std;
int f1[41] = {0, 1}, f0[41] = {1, 0}, t, n;
int main() {
	for(int i = 2; i < 41; i++) {
		f1[i] = f1[i - 1] + f1[i - 2];
		f0[i] = f0[i - 1] + f0[i - 2];
	}
	cin >> t;
	for(int i = 0; i < t && cin >> n; i++)
		cout << f0[n] << " " << f1[n] << endl;
}