피보나치 함수 (feat. 백준, 1003번)

피보나치 함수
https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/1003
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register int ans1[41] = { 0 }, ans2[41] = { 0 };				// N에 대한 0의 개수를 담는 ans1과 1의 개수를 담는 ans2
	ans1[0] = 1, ans2[0] = 0, ans1[1] = 0, ans2[1] = 1;
	for (register int n = 2; n <= 40; ++n)
		ans1[n] = ans1[n - 2] + ans1[n - 1], ans2[n] = ans2[n - 2] + ans2[n - 1];

	register int T;
	cin >> T;
	for (register int t = 0, v; t < T; ++t)
		cin >> v, cout << ans1[v] << " " << ans2[v] << endl;

	return 0;
}
// *&)*@*

1. 0과 1의 개수를 [A,B]로 표현한다고 하면, 0 = [1,0], 1 = [0,1], 2 = [1,1], 3 = [1,2], 4 = [2,3], ... 임을 알수 있습니다.
2. 여기서 식을 도출할 수 있으니 Ai = Ai-2 + Ai-1 입니다. 즉, 4의 결과 = 3의 결과 + 2의 결과 의 형태입니다.