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

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

 

---

 

코드

---

#include <iostream>
using namespace std;

int a[41] = { 0,1, };

int fibonacci(int num)
{
	if (num == 0 || num == 1) return a[num];
	//값이 없을 때만 재귀호출
	else if (a[num] == 0) a[num] = fibonacci(num - 1) + fibonacci(num - 2);
	return a[num];
	
}
int main() {
	int T, n;
	cin >> T;

	while (T--)
	{
		cin >> n;
		if (n == 0)
			cout << "1 0" << '\n';
		else {
			fibonacci(n);
			cout << a[n-1] << ' ' << a[n] << '\n';
		}
	}
}

 

 

 

---

 

 

시간제한 내에 풀어야 하기 때문에 동적 계획법(DP: Dynamic Programming)으로 문제를 해결해야 한다. (DP와 분할정복 차이 - https://galid1.tistory.com/507)

여기에서 0과 1 호출 횟수를 표로 나타내면 아래와 같다.

N	fibonacci(0) 횟수	fibonacci(1) 횟수
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5
6	5	8
7	8	13
8	13	21

위 표를 보면, fibonacci(0)과 fibonacci(1)의 호출 횟수도 피보나치 수열을 따른다는 것을 알 수 있다. 다만  fibonacci(0)에서는 첫 번째 항이 1이고 그 뒤부터  fibonacci(1)과 같은 수열이 나타난다.

이를 프로그램으로 나타내면 기존 피보나치 재귀호출 문제와 비슷해 보이지만, 피보나치 배열에 값이 이미 계산되어 있을 때엔 그 값을 가져다 쓴다. 값이 계산되어 있지 않았을 때 즉, 0일 때만 재귀호출을 하여 재귀호출 수를 크게 줄일 수 있다.