[C/C++]백준 2747번 - 피보나치 수

 

문제 링크 : https://www.acmicpc.net/problem/2747

2309번: 일곱 난쟁이

 

문제

입력받은 n번째 피보나치 수를 구하는 문제

---

접근방식

 

여러가지 방법으로 풀어 봤다. 나이나믹 프로그래밍 기법 연습하고 싶어서, 탑다운 방식과 바텀업 방식 2가지로 풀어봤다.

 

 탑다운 방식 코드

#include <iostream>
using namespace std;

int d[45] = { 0, };

int memo_fibo(int n)
{
	if (n == 0) return 0;
	else if (n == 1) return 1;
	else if (d[n] != 0) return d[n];

	d[n] = memo_fibo(n - 1) + memo_fibo(n - 2);
	return d[n];
}

int main()
{
	int N;
	int fibo;
	cin >> N;
	
	fibo = memo_fibo(N);
	
	cout << fibo << '\n';

	return 0;
}

 

바텀업 방식

#include <iostream>
using namespace std;

int d[45] = { 0, };

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

	for (int i = 2; i < n; i++)
	{
		d[i] = d[i - 1] + d[i - 2];
	}
	return d[n - 1];
}

int main()
{
	int N;
	int fibo;
	cin >> N;
	
	fibo = memo_fibo(N);
	
	cout << fibo << '\n';

	return 0;
}

 

이런 방식의 접근법은 처음 알게 되었는데, 알고리즘은 할수록 재밌는 방법들이 많다.

 

다른 문제의 코드 : https://github.com/DaeeYong/Algorithm-Solution-

DaeeYong/Algorithm-Solution-