[백준 1003] 피보나치 함수

https://acmicpc.net/problem/1003

---

해설

문제는 위와 같다.

일단, 시간 제한이 0.25초 라는 것을 보고 우리는 DP(다이나믹 프로그래밍)를 생각해봐야한다.

 

0과 1 리턴의 규칙성을 찾아보면 다음과 같다. 

 

fibo(n)	fibo 값	0의 개수	1의 개수
fibo(0)	0	1	0
fibo(1)	1	0	1
fibo(2)	1	1	1
˙˙˙
fibo(i)	fibo(i-1) + fibo(i-2)	fibo(i-1)	fibo(i)

 

처음 시작 항 두 개만 초기화 시켜주면 된다.

dp[0] = 0;
dp[1] = 1;

 

 

소스코드

 

#include <iostream>
using namespace std;
int dp[41];
int main(){
	int n; cin >> n;
	for(int l=0; l<n; l++){
		int a; cin >> a;
		dp[0] = 0;
		dp[1] = 1;
		for(int i=2; i<=a; i++)
			dp[i] = dp[i-1] + dp[i-2];
		if(a==0)
			cout << 1 << ' ' << 0 << '\n';
		else
		cout << dp[a-1] << ' ' << dp[a] << '\n';
	}
}