[백준 / BOJ] - 2748번 피보나치 수2 C++ 풀이

---

 

백준 - 단계별로 풀어보기 [2748] 

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

문제

 

 

 

풀이

 

일반적인 재귀를 활용한 피보나치 풀이법은, 풀이 방법 자체는 매우 간단하지만 이미 구했던 fibo(1), fibo(2), fibo(3), fibo(4)등의 값을 매번 다시 계산하기때문에 연산량이 과하게 많아 실행 속도가 매우 느리다.

 

본 문제는 시간 제한이 1초이고, n이 90까지이므로 재귀를 사용할경우 타임아웃이 발생하기 때문에, 

이미 구한 값들을 다시 활용하는 DP방식을 사용해야한다.

 

또한 Fibonacci 수열은 N이 커질수록 값이 급속도로 증가하므로 자료형은 long long을 사용한다.

코드

 

#include <iostream>
using namespace std;
long long fiboarr[100] = {0,1,};
long long fibo(int N)
{
    if(N == 0 || N == 1)
        return fiboarr[N];
    else if(fiboarr[N] == 0)
        fiboarr[N] = fibo(N-1) + fibo(N-2);
    return fiboarr[N];
}
int main() {
    int N;
    cin >> N;
    cout << fibo(N);
}

 

 

평가

 

자료형을 int가 아닌 long long으로 풀어야하며, 배열에 각 피보나치 수를 저장하는 방식으로 풀 수 있다면 간단히 해결이 가능한 문제이다. 거대한 문제를 작은 문제로 나누고, 이미 구한 값을 활용하는 DP 방법론에 대해서 잘 알아두고 넘어가자.