BOJ 1003번

피보나치 함수

1003번

문제

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

오답 코드(시간 초과)

#include <iostream>
using namespace std;

int zero_nums = 0;
int one_nums = 0;

void fibonacci(int n) {
	if (n == 0) {
		zero_nums += 1;
	}
	else if (n == 1) {
		one_nums += 1;
	}
	else {
		fibonacci(n - 1);
		fibonacci(n - 2);
	}
}

int main() {
	int test_case;
	cin >> test_case;

	for (int i = 0; i < test_case; i++) {
		int num;
		cin >> num;
		fibonacci(num);
		cout << zero_nums << " " << one_nums << endl;
		zero_nums = 0;
		one_nums = 0;
	}
}

문제점 및 해결방법

다음과 같이 호출한 횟수만 구하면 된다고 생각해서 단순하게 했더니 답을 올바르게 나오지만 재귀함수의 반복적인 호출로 인해 조건인 40이하에서도 시간이 상당히 소요되는 것을 문제를 틀리게 되어 확인할 수 있었다.

그래서 이 점을 어떻게 해결해야하는지에 대해 찾아봤고, Dynamics Programming 이라는 알고리즘을 알게 되어서, 이 방법을 적용해보았다.

동적 프로그래밍(동적 계획법)에 대해서는 공부를 해서 따로 포스팅하겠다.

본인 정답 코드

#include <iostream>
using namespace std;

int main() {
	int test_case;
	cin >> test_case;

	int* fibonacci_tbl = new int[41];
	fibonacci_tbl[0] = 0; fibonacci_tbl[1] = 1;

	for (int i = 2; i < 41; i++) {
		fibonacci_tbl[i] = fibonacci_tbl[i - 1] + fibonacci_tbl[i - 2];
	}

	for (int i = 0; i < test_case; i++) {
		int num;
		cin >> num;

		if (num == 0)
			cout << "1 0" << endl;
		else
			cout << fibonacci_tbl[num - 1] << " " << fibonacci_tbl[num] << endl;
	}

	delete[] fibonacci_tbl;
}

다시 미리 계산을 해놓는 방식으로 코드를 수정하였고, 기존처럼 하나의 fibonacci 값을 구하기 위해 이전의 연산들과 상관없이 다시 모든 수를 구하는 과정이 사라졌다.

결론, 피보나치 수열의 성질을 이용해 내부 값을 계속 저장해가며 표면적인 계산을 했다고 생각하면 된다.

📣
Baekjoon에서 맞은 코드만 업데이트합니다.
본 포스팅의 풀이 언어 및 개발 환경 : C++, VScode
풀이에 대한 문제나 궁금한 점은 Comments를 작성해주시면, 많은 도움이 됩니다.💡