다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.
int fibonacci(int n) {
if (n == 0) {
printf("0");
return 0;
} else if (n == 1) {
printf("1");
return 1;
} else {
return fibonacci(n‐1) + fibonacci(n‐2);
}
}
fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.
첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
#include <iostream>
using namespace std;
/* 조건 */
#define MAX_INPUT 41
/* 변수 */
int T, N;
int fibo[MAX_INPUT][2];
/* 함수 */
void makeFiboArray() {
fibo[0][0] = 1;
fibo[0][1] = 0;
fibo[1][0] = 0;
fibo[1][1] = 1;
for(int i = 2; i < 41; i++) {
fibo[i][0] = fibo[i-1][0] + fibo[i-2][0];
fibo[i][1] = fibo[i-1][1] + fibo[i-2][1];
}
}
void printResult(int n) {
cout << fibo[n][0] << ' ' << fibo[n][1] << '\n';
}
int main() {
/* Fast cin cout */
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
/*****************/
/* 풀이 */
makeFiboArray();
/* 입력 */
cin >> T;
for(int i = 0; i < T; i++) {
cin >> N;
printResult(N);
}
}
fibonacci(N)은 fibonacci(N-1)과 fibonacci(N-2)를 호출하므로,
fibonacci(0)과 fibonacci(1)이 누적되어 호출되므로, 배열을 만들어 각 N에 대한 값을 저장하고, 입력된 N에 해당하는 값을 출력한다.