#1003 피보나치 함수

# 문제

# 입력 및 출력

# 풀이

간단하게 dp로 풀면 된다

f(0)과 f(1)의 0, 1 호출 횟수를 pair 배열에 저장해두고

f(2)부턴 f(n-1), f(n-2)의 0, 1 호출 횟수를 더해주면 됨

N은 40보다 작거나 같은 자연수, 0 이므로 pair 배열 크기는 41로 설정해주면 됨

#include <iostream>
using namespace std;

int main() {
	pair<int, int> dp[41];
	dp[0] = make_pair(1, 0);
	dp[1] = make_pair(0, 1);
	for (int i = 2; i < 41; i++) {
		dp[i].first = dp[i - 1].first + dp[i - 2].first;
		dp[i].second = dp[i - 1].second + dp[i - 2].second;
	}
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		int N;
		cin >> N;
		cout << dp[N].first << " " << dp[N].second << "\n";
	}
}

pair 배열 대신 2차원 배열로 풀어도 됨