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

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

1003번: 피보나치 함수

 

백준 1003번을 풀어봤습니다.

간단한 다이나믹 프로그래밍 문제입니다.

재귀 함수를 그대로 사용하면 시간이 너무 오래걸려서 결과값을 저장하는 배열을 만들어주면 됩니다.

재귀 함수 첫 부분에 이미 계산한 값인지만 체크해주는 if문만 만들면 됩니다.

 

아래는 전체 코드입니다.

#include <iostream>
using namespace std;

int callCount[40][2];


pair<int,int> fibonacci(int n) {
    if (callCount[n][0] != 0 || callCount[n][1] != 0) {
        return pair<int, int>(callCount[n][0], callCount[n][1]);
    }

    if (n == 0) {
        //printf("0");
        return pair<int, int>(1, 0);

    }
    else if (n == 1) {
        //printf("1");
        return pair<int, int>(0, 1);
    }
    else {
        int f1 = fibonacci(n - 1).first;
        int s1 = fibonacci(n - 1).second;
        int f2 = fibonacci(n - 2).first;
        int s2 = fibonacci(n - 2).second;
        callCount[n][0] = f1 + f2;
        callCount[n][1] = s1 + s2;
        return pair<int, int>(f1 + f2, s1 + s2);

    }
}

int main() {
	callCount[0][0] = {1};
	callCount[1][1] = {1};

	int t, n;
	cin >> t;

	while (t--) {
		cin >> n;
        fibonacci(n);
        cout << callCount[n][0] << ' ' << callCount[n][1] << '\n';
	}

    return 0;
}