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

피보나치 수 2

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

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초128 MB81352329452704640.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

10

예제 출력 1

55

비슷한 문제

알고리즘 분류


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


주의 사항

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

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

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

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

통과된 코드

#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 <- 피보나치 수를 구하는 여러가지 방법

“백준 2748번 (피보나치 수 2, C++, DP) [BAEKJOON]”에 대한 1개의 생각

  1. 핑백: 백준 10826번 (피보나치 수 4, C++, DP) [BAEKJOON] - 어제와 내일의 나 그 사이의 이야기

댓글 달기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다

위로 스크롤