C++ 피보나치 수 2 - 백준 알고리즘

2748번 피보나치 수 2

---

문제

---

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

10

출력

---

첫째 줄에 n번째 피보나치 수를 출력한다.

55

정답

---

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

long long fibonacci_topdown(int n)
{
	static long long memo[90] = { 0 };	// 중간 중간에 나오는 거 저장할 용도

	if (n == 0 || n == 1) return n;

	if (memo[n] > 0)	// 0보다 크면 이전에 계산해서 저장해 놓은 것
		return memo[n];

	// 계산 안 되어 있으면 계산하고 저장

	memo[n] = fibonacci_topdown(n - 1) + fibonacci_topdown(n - 2);

	return memo[n];
}

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

	int N = 0;

	cin >> N;

	cout << fibonacci_topdown(N) << endl;

	return 0;
}

피보나치 수열 문제를 Dynamic Programming을 사용하여 풀어보았습니다.
Dynamic Programming은 Top-down 방식과 Bottom-up 방식이 있습니다. 그 중 Top-dwon방식을 사용하여 코딩해보았습니다.

인풋으로 최대 90이 들어갈 수 있으므로 int형을 사용하면 안됩니다. int형의 경우 46까지만 수열을 풀 수 있습니다.

그렇기 때문에 long long형을 사용하여 풀어야 합니다.

---