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

문제: 1003번: 피보나치 함수

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
//#include <bits/stdc++.h>

using namespace std;

int zeroCnt = 0;
int oneCnt = 0;

// first: 0 count, second: 1 count
vector<pair<int, int>> table; // 0~41

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t;
	cin >> t;
	while (t-- > 0) {
		int n;
		cin >> n;

		table = vector<pair<int, int>>(n + 1);
		table[0] = make_pair(1, 0);
		if (n > 0) {
			table[1] = make_pair(0, 1);
		}
		for (int i = 2; i < n + 1; i++) {
			int zeroCnt = table[i - 1].first + table[i - 2].first;
			int oneCnt = table[i - 1].second + table[i - 2].second;
			table[i] = make_pair(zeroCnt, oneCnt);
		}

		cout << table[n].first << " " << table[n].second << "\n";
	}
	return 0;
}

 

그냥 dp 성질만 잘 알고 있으면 쉽게 해결할 수 있는 문제이다. 나는 pair 를 이용해서 각 피보나치의 0의 개수와, 1의 개수를 저장했다.

 

마지막에 table[n] 의 0, 1 의 개수를 출력해주면 된다.