[백준 1003] 피보나치 함수

요구사항

피보나치 수열을 구현하였을때, 0과 1의 출현 횟수 구하기

 

풀이

바텀업 방식으로

 d0, d1 배열을 잡아서 d0의 출현 횟수, d1의 출현 횟수를 구한다

d0는 d0만의 피보나치 함수이고

d1은 d1만의 피보나치 함수이다.

 

#pragma warning(disable:4996)
#include <vector>
#include <queue>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <functional>
#include <algorithm>

using namespace std;
int d0[51];
int d1[51];
int main() {
	d0[0] = 1;
	d0[1] = 0;
	d1[0] = 0;
	d1[1] = 1;
	int t;
	for (int i = 2; i <= 41; i++) {
		d0[i] = d0[i - 1] + d0[i - 2];
		d1[i] = d1[i - 1] + d1[i - 2];
	}
	scanf("%d", &t);
	for (int tc = 1; tc <= t; tc++) {
		int x;
		scanf("%d", &x);
		printf("%d %d\n", d0[x], d1[x]);
	}
}