[C++][백준 1003][다이나믹 프로그래밍] 피보나치 함수 :: seoftware

 문제 

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

1003번: 피보나치 함수

 소스 

#include <iostream>
using namespace std;
int cnt[41][2];

void fibonacci(int n) {
	cnt[0][0] = 1; cnt[0][1] = 0;
	cnt[1][0] = 0; cnt[1][1] = 1;
	for (int i = 2; i <= n; i++) {
		cnt[i][0] = cnt[i - 1][0] + cnt[i - 2][0];
		cnt[i][1] = cnt[i - 1][1] + cnt[i - 2][1];
	}
}
int main(void) {
	int k;
	cin >> k;
	
	for (int i = 0; i < k; i++) {
		int n;
		cin >> n;
		fibonacci(n);
		cout << cnt[n][0] << " " << cnt[n][1] <<endl;
	}
	return 0;
}

1. 이차원배열 cnt를 선언한다 : cnt[n][0] 은 숫자 n의 0 호출 횟수이고, cnt[n][1]은 n의 1 호출 횟수.

2. 문제에 나와있는 재귀 코드를 그대로 사용하고 n==0일때와 1일때 각각 카운트 해주면 시간초과 발생!    (이 이유에 대해서는 아래 참고에 있는 글을 보면 좋을 것 같다!)

 참고 

2020/02/20 - [IT/자료구조, 알고리즘] - [알고리즘] 동적 프로그래밍, 다이나믹 프로그래밍, DP :: seoftware

[알고리즘] 동적 프로그래밍, 다이나믹 프로그래밍, DP :: seoftware