[210415][백준/BOJ] 2747번 피보나치 수

문제

입출력

---

풀이

피보나치 수열은 재귀를 이용해서 풀 수 있으며 재귀의 시간복잡도는 O(2^n)이다. n이 30을 넘어가는 이후부터는 일반 컴퓨터로 출력을 할 수가 없다.
따라서 피보나치는 dp를 이용해서 문제를 풀어야 한다.

피보나치 수열의 점화식은 f(n) = f(n-1) + f(n-2) 이며 초기값은 f(0)=0, f(1)=1 이다.
이를 이용해서 재귀를 이용하는 top-down 방식과 반복문을 이용하는 bottom-up 방식으로 풀었다.

코드

top-down 방식

#include <bits/stdc++.h>
using namespace std;

int d[102];

int dp(int n)
{
	if (n == 1) return 1;
	if (n == 2) return 1;

	if (d[n] != 0) return d[n];
	d[n] = dp(n - 1) + dp(n - 2);
	return d[n];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	cout << dp(n);
}

bottom-up 방식

#include <bits/stdc++.h>
using namespace std;

int d[102];

int dp(int n)
{
	d[0] = 0;
	d[1] = 1;

	for (int i = 2; i <= n; ++i)
		d[i] = d[i - 1] + d[i - 2];
	return d[n];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	cout << dp(n);
}