[백준] 1003번 피보나치 함수 C++ 문제풀이

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

1003번: 피보나치 함수

문제 풀이

처음에는 재귀 함수 안에 count를 했는데, 시간초과가 나왔다.

따라서 pair<int,int> fibo 배열을 만들어서 first에는 0이 나오는 횟수, second에는 1이 나오는 횟수를 저장하고

2부터 40까지 증가하는 순서로 배열을 채웠다.

소스 코드

#include <iostream>
using namespace std;

pair<int, int> fibo[41];

int main() {
	int T;
	cin >> T;
	//fibo 배열 만들기
	fibo[0].first = 1;
	fibo[0].second = 0;
	fibo[1].first = 0;
	fibo[1].second = 1;
	for (int i = 2; i <= 40; i++) {
		fibo[i].first = fibo[i - 1].first + fibo[i - 2].first;
		fibo[i].second = fibo[i - 1].second + fibo[i - 2].second;
	}

	for (int i = 0; i < T; i++) {
        int num;
        cin >> num;
		cout << fibo[num].first << ' ' << fibo[num].second << '\n';
	}
}