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

문제 링크

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

기본적인 피보나치 문제를 모르거나 시간초과가 문제라면

http://degurii.tistory.com/14?category=755814

를 참고하자.

기존의 피보나치 함수가

$$f(n) = f(n - 2) + f(n - 1)$$

이므로

$n$일때 호출되는 0과 1의 개수를 $[$0의개수, 1의개수$]_n$ 로 표현해서 단순히

$[i, j]_n = [i, j]_{n - 2} + [i, j]_{n - 1}$ 처럼 쓸 수 있다.

이때, $[i, j] + [x, y] = [i + x, j + y]$로 정의한다.

정답 코드

	#include <iostream>
	using namespace std;
	using pii = pair<int, int>;
	int n, t;
	pii d[50];
	pii operator + (const pii &a, const pii &b) {
	return { a.first + b.first, a.second + b.second };
	}
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	d[0] = { 1, 0 };
	d[1] = { 0, 1 };
	for (int i = 2; i <= 40; i++) {
	d[i] = d[i - 1] + d[i - 2];
	}
	cin >> t;
	while (t--) {
	cin >> n;
	cout << d[n].first << ' ' << d[n].second << '\n';
	}
	}

view raw 1003.cpp hosted with ❤ by GitHub