#include <iostream>

using namespace std;


typedef struct fibonacci {

int zero;

int one;

}Fibo;


const int MAX_INPUT = 40;


void Initialize(Fibo* fibo)

{

fibo[0].zero = 1;

fibo[0].one = 0;

fibo[1].zero = 0;

fibo[1].one = 1;

}


void Memorization(Fibo* fibo)

{

for (int i = 2; i <= MAX_INPUT; i++)

{

fibo[i].zero = fibo[i - 1].zero + fibo[i - 2].zero;

fibo[i].one = fibo[i - 1].one + fibo[i - 2].one;

}

}


int main(void)

{

Fibo fibo[MAX_INPUT + 1];

int input, T;


Initialize(fibo);

Memorization(fibo);


cin >> T;

for (int i = 0; i < T; i++)

{

cin >> input;

cout << fibo[input].zero << " " << fibo[input].one << endl;

}

}


내가 한건 메모리제이션으로 미리 답을 구해서 캐시하는 방법인데 이거 말구~


그때그때 다이나믹하게 풀어내는 방법이 있을까 ^^?


내가 어렴풋이 떠오르는건 재귀 트리에서 말단 노드의 갯수가 2^n-1개라는 것에 아이디어가 생각날듯 말듯한데..!! ^^;


배열 40개를 안쓰고..!