백준 2748번 (피보나치 수 2, C++, DP) [BAEKJOON]

문제

https://www.acmicpc.net/problem/2748

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	81352	32945	27046	40.142%

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

출력

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

예제 입력 1

csharp

예제 출력 1

csharp

알고리즘 분류

전에 풀었던 문제를 참고하여 접근했습니다. (DP 방법)

백준 24416번 (알고리즘 수업 - 피보나치 수 1, C++, DP)

비슷한 문제

주의 사항

n은 90보다 작거나 같은 자연수

int로 값을 처리하면 오버플로우가 발생합니다.

그래서 long long int로 처리해 주었습니다.

전의 문제와 약간의 차이가 있는 부분은 0번째 항부터 시작한다는 것입니다.

통과된 코드

cpp

#include <iostream>

using namespace std;

int N;

// N이 90일 경우 int로 처리하면 
// 21억을 넘어가서 오버플로우가 발생한다. 
long long int arr[91];

long long int FibonacciDP(int N)
{
	arr[0] = 0;
	arr[1] = 1;

	for (int i = 2; i <= N; i++) {
		arr[i] = arr[i - 1] + arr[i - 2];
	}

	return arr[N];
}

int main()
{
	cin >> N;
	cout << FibonacciDP(N);
	return 0;
}

위의 코드로 백준 2747, 10870번 문제도 통과가 가능합니다. (N의 범위 차이만 있음)

https://www.acmicpc.net/blog/view/28 <- 피보나치 수를 구하는 여러가지 방법