백준 1003: 피보나치 함수 (C++)

문제 링크: www.acmicpc.net/problem/1003

 

피보나치 함수를 구현하는 여러 방법이(재귀 함수 등)있지만 기존의 값을 저장하지 않고 새로운 숫자의 피보나치 값을 구하려면 이전 값까지 계속 다시 연산해야 한다.

예를 들어, 새롭게 숫자 5의 피보나치 결과를 구하려면 이전에 피보나치 4, 3, 2, 1을 구했더라도 새롭게 다시 연산해야 한다. 다른 숫자에 대해서도 기존에 연산한 결과를 활용하지 못하고 새롭게 연산해야하므로 답은 제대로 나오겠지만 시간이 많이 걸리게 된다.

이 문제는 제한시간이 0.25초로 위 방법을 사용하면 시간 초과가 뜬다.

그럼 어떻게 시간 초과를 피할 수 있을까?

답은 다이나믹 프로그래밍(동적 계획법)이다.

 

다이나믹 프로그래밍(동적 계획법)이란?

기존의 연산 결과를 저장하고 저장한 연산 결과를 재활용하는 기법이다.

 

N은 40보다 작거나 같은 자연수 또는 0이라고 문제에서 제시해주었으므로 0~40까지의 피보나치 함수 결과값들을 미리 계산한다. 이때 작은 수부터 시작해서 배열에 저장해두면 그 다음 수에서 새롭게 계산하지 않고 기존의 값을 재활용할 수 있다.

 

#include <cstdio>

int fib[41]; //피보나치 연산 결과 저장
//0프린트 횟수 : fib(k-1) , 1프린트 횟수: fib(k)

void fibonacci() {  //다이나믹 프로그래밍 기법 사용_배열에 피보나치 결과 저장해서 재이용
	for (int i = 0; i <= 41; i++) {
		if (i == 0) {
			fib[i] = 0;
		}
		else if (i == 1) {
			fib[i] = 1;
		}
		else {
			fib[i] = fib[i - 1] + fib[i - 2];
		}
	}
}

int main() {
	int caseNum, input;
	fibonacci();

	scanf("%d", &caseNum);
	for (int i = 0; i < caseNum; ++i) {
		scanf("%d", &input);
		if (input == 0) printf("%d %d\n",1,0);
		else printf("%d %d\n", fib[input-1], fib[input]);
	}
}