[동적계획법, 난이도 중하] 백준 1003번 피보나치 함수

피보나치 함수 fibonacci(n) 의 리턴값은 fibonacci(n-1)+fibonacci(n-2) 이다.

fibonacci(0)은 0을 출력하므로 0이 1회 출현한다고 보고

fibonacci(1)은 1을 출력하므로 1이 1회 출현한다고 본다.

그렇다면 fibonacci(2)는 fibonacci(1)과 fibonacci(0)을 리턴하기 때문에

0,1이 1회씩 출현한다고 할 수 있다.

 

fibonacci(3)까지 해보자.

fibonacci(3)은 fibonacci(2)와 fibonacci(1)을 리턴하기 때문에

0은 1회, 1은 2회 출현한다고 할 수 있다.

 

자세히 나타내면 이렇다.

fibonacci(2) -> 0 1회, 1 1회

fibonacci(1) -> 0 0회, 1 1회 

fibonacch(3) 총 0 1회, 1 2회

 

fibonacci(n)에서 0의 출현횟수는 fibonacci(n-1)의 0 출현횟수 + fibonacci(n-2)의 0 출현횟수

fibonacci(n)에서 1의 출현횟수는 fibonacci(n-1)의 1 출현횟수 + fibonacci(n-2)의 1 출현횟수

n=10까지 모두 나타내보면 이렇다.

 

 

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <math.h>
#include <stack>
int save0[41];
int save1[41];
using namespace std;
int main() {
	int t;
	cin >> t;
	save0[0] = 1;
	save1[0] = 0;
	save0[1] = 0;
	save1[1] = 1;
	for (int i = 2; i < 41; i++) {
		save0[i] = save0[i - 1] + save0[i - 2];
		save1[i] = save1[i - 1] + save1[i - 2];
	}
	for (int i = 1; i < t + 1; i++) {
		int n;
		cin >> n;
		cout << save0[n] << " " << save1[n] << endl;
	}
}