[백준] 1003번 피보나치 함수

1003번: 피보나치 함수

순진하게 문제에 나와있는 대로 재귀를 해버리면 시간 초과 난다.

게다가 테스트 케이스 만큼 값을 여러 번 출력해야 하기 때문에 메모이제이션으로 풀어준다.

 

N을 입력 받기 전에 미리 벡터에 0이 출력되는 횟수와 1이 출력되는 횟수를 저장시켜놓고

N을 받으면 거기서 바로 꺼내와 출력시키도록 하면 된다.

#include <iostream>
#include <vector>
using namespace std;
int zero = 0, one = 0;
vector < pair<int, int> > fibonacci;

int main() {
	fibonacci.push_back(pair<int, int>(1, 0));
	fibonacci.push_back(pair<int, int>(0, 1));

	for (int i = 2; i <= 40; i++) {
		int zero1 = fibonacci[i - 1].first, zero2 = fibonacci[i - 2].first;
		int one1 = fibonacci[i - 1].second, one2 = fibonacci[i - 2].second;
		fibonacci.push_back(pair<int, int>(zero1 + zero2, one1 + one2));
	}

	int T;
	cin >> T;

	int N;
	for (int t = 0; t < T; t++) {
		cin >> N;
		cout << fibonacci[N].first << " " << fibonacci[N].second << "\n";
	}
	return 0;
}