[백준] 1003번: 피보나치 함수

문제링크 : https://www.acmicpc.net/problem/1003

 

문제풀이

정답 비율이 29%로 낮아서 어려운 문제인 줄 알았는데.. 왜 이렇게 낮은지 모르겠다.

 

1) fibonacci(2) 호출 시

fibonacci(1) 호출 --- 1 출력

fibonacci(0) 호출 --- 0 출력

 

2) fibonacci(3) 호출 시

fibonacci(2) 호출 --- 1, 0 출력

fibonacci(1) 호출 --- 1 출력

 

여기에서 fibonacci(2)는 또 구할 필요 없이 1번에서 구한 개수를 가져다 쓰면 된다.

 

따라서 fibonacci(N)을 호출했을 때 출력되는 개수는

fibonacci(N-1)을 호출했을 때 출력되는 개수 + fibonacci(N-2)를 호출했을 때 출력되는 개수와 같다.

 

문제에서 N은 최대 40으로 큰 값이 아니어서, 40까지의 개수를 미리 구해놓은 후 출력했다.

 

소스코드

/*
 * 백준 1003번: 피보나치 함수
 */

#include <iostream>

using namespace std;

#define MAX 41

int fibonacci[2][MAX];

int main() {
	fibonacci[0][0] = 1;
	fibonacci[1][1] = 1;

	for (int i = 2; i < MAX; i++) {
		fibonacci[0][i] = fibonacci[0][i - 1] + fibonacci[0][i - 2];
		fibonacci[1][i] = fibonacci[1][i - 1] + fibonacci[1][i - 2];
	}

	int T;
	cin >> T;
	while (T--) {
		int N;
		cin >> N;
		
		cout << fibonacci[0][N] << " " << fibonacci[1][N] << endl;
	}

	return 0;
}