BaekJoon(1003)::피보나치 함수

문제

1003번: 피보나치 함수

문제파악

피보나치수열 아마 쉽게 알 수 있는 문제일 것이다. 

피보나치 수열이란?
첫째 및 둘째 항이 1이며 그 뒤의 모든 항이 바로 앞 두 항의 합인 수열

그렇다면, 이 문제는 피보나치수열에서 무엇을 원하는 건지 알아봐야 한다.

피보나치수열의 점화식은 다음과 같다

$$f(n) = f(n-1)+f(n-2) \quad and \quad n \geqq 2$$

 

정의상 n은 3 이상일 수 있지만 편의상 0번째 항의 값을 0으로 생각한다면 2 이상으로 생각해도 무관하다.

그리고 피보나치를 재귀로 구현하면 다음과 같다.

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);
    }
}

이때 결국 n의 값이 0과 1이 호출되는 경우가 생기는데 이때의 0과 1의 각 호출 수를 구하면 된다.

문제풀이

해당 문제도 결국 dp로 귀결되는데 기존 피보나치수열을 구할 때 생각해보면 재귀를 완전히 진행시켜돼 되지만 메모이제이션을 통해 f(n)을 호출 시 이미 f(n-1)과 f(n-2)의 값이 존재할 경우 해당 값에서 값을 가져온다.

 

즉, 해당 문제도 똑같을 것이다.

예를 들어, f(4)을 호출시 f(3)를 호출했을 때의 f(0), f(1)의 호출 횟수를 그리고 f(2)를 호출했을때의 f(0),f(1)의 호출횟수를 메모이제이션 처리를 해두면 속도측면에서 문제없이 해결할 수 있게 된다.

 

우선 해당 케이스가 맞는지 짧게 확인해보면 다음과 같다

	fibonacci(0)	fibonacci(1)
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5

표를 통해서 확인한 바와 같이 정리할 수 있음을 알 수 있다.

 

해당 문제도 메모이제이션을 사용하면 재귀 혹은 반복문을 통해서 문제를 해결할 수 있다.

해결책 1(반복문)

#include<iostream>
using namespace std;

int main() {
	int fibo_call[41][2];

	fibo_call[0][0] = fibo_call[1][1] = 1;
	fibo_call[1][0] = fibo_call[0][1] = 0;

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

	int t_case;
	cin >> t_case;

	while (t_case--) {
		int n;
		cin >> n;
		cout << fibo_call[n][0] << " " << fibo_call[n][1] << endl;
	}

	return 0;
}