알고리즘 수업 - 피보나치 수 1 (feat. 백준, 24416번)

알고리즘 수업 - 피보나치 수 1
https://www.acmicpc.net/problem/24416

24416번: 알고리즘 수업 - 피보나치 수 1

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/24416
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, fb[41];
	fb[1] = fb[2] = 1;
	cin >> N;
	for (register int i = 3; i <= N; ++i)
		fb[i] = fb[i - 1] + fb[i - 2];
	cout << fb[N] << " " << N - 2 << "\n";
	return 0;
}
// *&)*@*

1. 재귀에 의한 피보나치 수열의 개수는 F[N] = F[N - 1] + F[N - 2] 가 되고 dp를 이용한 피보나치 수열은 N - 2번의 수행이 성립됩니다.