[DP] BOJ 1003 피보나치 함수

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

1003번: 피보나치 함수

우선 피보나치 함수를 구현할 때는 두 가지 방식으로 구현을 할 수 있다.

 

첫번째 방식 - 재귀

문제의 코드처럼 계속해서 재귀적으로 함수를 호출해서 1 또는 0이 되게 만드는 방식이다.

그렇게 되면 만약 5라는 값이 함수에 들어오게 되면 fib(3)과 fib(4)로 나뉘게 되고

또 그 두 함수들도 계속 쪼개지다가 0과 1이 될 때, 함수 호출을 멈추게 된다.

그렇게 되면 했던 계산을 계속 되풀이할 뿐만 아니라 시간적으로도 엄청난 손해를 보게되는 방식이다.

 

두 번째 방식 (정답 코드) - DP

두 번째 방식으로는 DP(다이나믹 프로그래밍)을 이용하는 것이다.

위의 방식에서는 불필요한 계산을 반복했지만 DP를 이용하면 전에 계산했던 값들을 전부 배열에 저장하기 때문에

나중에 같은 계산을 할 때, 그대로 가져다 쓰기만 하면 된다.

#include <iostream>
#include <vector>
using namespace std;

int zero[50] = { 1,0, }, one[50] = { 0,1, };

void zerofibonacci(int k) {
	for (int i = 2; i <= k; i++) {
		zero[i] = zero[i - 1] + zero[i - 2];
	}
}
void onefibonacci(int k) {
	for (int i = 2; i <= k; i++) {
          
		one[i] = one[i - 1] + one[i - 2];
	}
}
int main() {
	int a; cin >> a;
	while (a--) {
		int k; cin >> k;
		if (k >= 2 && one[k] == 0 && zero[k] == 0) {
			onefibonacci(k); zerofibonacci(k);
		}
		cout << zero[k] << ' ' << one[k] << '\n';
	}
}

이 문제에서는 들어오는 값에 대한 0이 호출되는 횟수와 1이 호출되는 횟수를 각각 물어보는 문제이기 때문에, 서로

다른 배열로 구현해서 각각 계산을 하였다.