[1003] 피보나치 함수, c++

한줄 후기 : 그냥 재귀로 불러 ... 

 

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

1003번: 피보나치 함수

 

다이나믹 프로그래밍 사용

dp배열을 0, 1저장할 거 두개 만들어서 피보나치 돌리면 된다.

 

#include <iostream>
using namespace std;
void fibo(int n) {
	int dp1[42];
	int dp2[42];
	dp1[0] = 1;
	dp2[0] = 0;
	dp1[1] = 0;
	dp2[1] = 1;
	for (int i = 2; i <= 40; i++) {
		dp1[i] = dp1[i - 1] + dp1[i - 2];
		dp2[i] = dp2[i - 1] + dp2[i - 2];
	}
	cout << dp1[n] << " " << dp2[n] << endl;
	return;
}
int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		fibo(n);
	}
}