[C++] 백준(BOJ) - 2747 : 피보나치 수열

12 Apr 2024 in Develop on C++, Algorithm

• 문제
• 입력
• 출력
• 알고리즘
• 풀이
• 코드 1 : Top down
• 코드 2 : Bottom up
• 평가

문제

BOJ - 2747 : 피보나치 수열(링크)

피보나치 수는 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은 45보다 작거나 같은 자연수이다.

출력

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

알고리즘

1. DP
2. Top Down & Bottom Up

풀이

• 기저사례, 메모이제이션, 메인로직, 초기화를 활용
• Top down 방식을 쓰기 위해서는 메모이제이션이 시간복잡도상 필수인 경우가 많음
• 점화식을 만들어서 풀어나가는 Bottom Up 방법도 익숙해지기

코드 1 : Top down

// BOJ - 2747 : 피보나치 수
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, dp[50] = { 0, 1 };

ll fib(int n)
{
	if (n == 0) return 0;
	if (n == 1) return 1;
	if (dp[n] != 0) return dp[n];
	dp[n] = fib(n - 2) + fib(n - 1);
	return dp[n];
}

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

	cin >> n;

	cout << fib(n) << '\n';

	return 0;
}

코드 2 : Bottom up

// BOJ - 2747 : 피보나치 수
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, dp[50] = { 0, 1 };

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

	cin >> n;

	dp[0] = 0;
	dp[1] = 1;

	for (int i = 2; i <= n; i++)
	{
		dp[i] = dp[i - 2] + dp[i - 1];
	}
	cout << dp[n] << '\n';

	return 0;
}

평가

• DP의 기본유형 2가지 (Top Down, Bottom Up)
• DP의 풀이 방법
  • 기저사례
  • 메모이제이션
  • 로직
  • 초기화