백준 1003번 피보나치 함수

백준 1003번은 기초적인 동적 계획법(DP, Dynamic programming) 문제입니다. 시간제한이 0.25초로 매우 빡빡한 편이라서 시간복잡도 O(n)으로 풀어야 해결 가능합니다.

 

다음 소스는 문제에서 주어진 $N$번째 피보나치 수를 구하는 C++ 함수입니다.

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이 각각 몇번씩 return되는지 구하는 문제인데, $fib(n)$ 을 $n$번째 피보나치 숫자를 반환하는 함수라고하면, $fib(0)$과 $fib(1)$의 경우를 제외하면 0이 return되는 횟수는 $fib(n-2)$회, 1이 return되는 횟수는 $fib(n-1)$회라는 규칙을 발견할 수 있습니다.

 

우리가 흔히 아는 이 문제의 해결법인 재귀를 통한 풀이(물론 이 문제에도 소스가 소개되어 있다)에 메모이제이션을 더해주면 얕게나마 동적 계획법의 우아함을 맛볼 수 있습니다.

#include<iostream>
using namespace std;
int memo[41] = { 1,1, }; //n이 0, 1일때 초기값 설정
int fib(int n) {
	if (n <= 1) return memo[n];
	else if (memo[n] > 0) return memo[n];
	return memo[n] = fib(n - 1) + fib(n - 2);
}
int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		if (n == 0) cout << "1 0\n"; //n이 0일때 예외처리
		else if (n == 1)cout << "0 1\n"; //n이 1일때 예외처리
		else {
			fib(n);
			cout << memo[n - 2] << " " << memo[n - 1] << "\n";
		}
	}
	return 0;
}