피보나치 수 2
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
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 <- 피보나치 수를 구하는 여러가지 방법
핑백: 백준 10826번 (피보나치 수 4, C++, DP) [BAEKJOON] - 어제와 내일의 나 그 사이의 이야기