백준 1003 피보나치 함수

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 n번째 피보나치 함수를 구할 때 1번째 피보나치 수와 0번째 피보나치 수가 각각 몇번 나왔는지를 구하는 문제입니다.

 

기본적으로 피보나치 함수를 구할 때 f(n) = f(n-1)+f(n-2) 인 성질을 이용하여 pair를 자료형으로 가지는 벡터를 하나 선언해 first 에는 0의 개수 second에는 1의 개수를 넣어주면서 구해주면 됩니다. 

v[i].first =  v[i-1].first + v[i-2].first, v[i].second = v[i-1].second + v[i-2].second 대략 이런식으로 저장이 되어 n번째 까지 진행을 하면 답을 구할 수 있습니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <vector>
using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	vector<pair<int, int>> v;
	v.push_back(make_pair(1, 0));
	v.push_back(make_pair(0, 1));
	
	for(int i = 2; i <= 40; i++) {
		v.push_back(make_pair(v[i-1].first + v[i-2].first, v[i-1].second + v[i-2].second));
	}
	int T;
	cin >> T;
	while(T--) {
		int n;
		cin >> n;
		cout<<v[n].first<<' '<<v[n].second<<'\n';	
	}
	
	return 0;
}