[백준 2748] 피보나치 수2

• 안녕하세요. BlockDMask 입니다.

• 제가 과거(17년 8월)에
  피보나치 수 문제 에서 재귀함수로 풀었을때, 
  시간 초과가 난다고 판단하여 반복문으로 풀었던 적이 있었습니다.

• 오늘 아침일찍
  "큰돌"님 께서 이미 계산한 값을 캐싱(저장)함으로서
  또다시 계산하는 시간을 줄여서 푸는
  방법이 있다고 댓글을 달아주셨습니다.
  (가르침을 주셔서 감사합니다.)

• 그러한 방법으로 피보나치 수 2문제를 풀어 봤습니다.

0. 제목

• 백준 2748 피보나치 수2

• BOJ 2748 피보나치 수2

• C/C++ Fibonacci 

1. 문제 설명

• 피보나치 수는 0과 1로 시작한다.
  0번째 피보나치 수는 0이고
  1번째 피보나치 수는 1이다.

• 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.
  이를 식으로 써보면 Fn = F(n-1) + F(n-2) (n>=2) 가 됩니다.

• n= 17일때 까지 피보나치 수를 써보면 다음과 같습니다.
  0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 477, 610, 987, 1597

• n이 주어졌을 때, n 번째 피보나치 수를 구하는 프로그램을 작성하시오.

--입력--

첫째 줄에 n이 주어집니다. n 은 90보다 작거나 같은 자연수 입니다.

--출력--

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

2. 풀이 과정

• 위에서 언급하였듯이 recursive를 이용하여 풀었습니다.

• 한번 계산한 수는 저장하여 다시 계산하는데 드는 오버헤드를 줄였습니다.

• memset을 이용하여 초기 cache배열의 값들을 -1로 setting 하였습니다.

• 90번째 피보나치 수 까지 담아야 하므로 자료형은 long long 으로 결정하였습니다.

3. 소스 코드

//https://www.acmicpc.net/problem/2748
//BOJ_2748_fibonacci2
 
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
 
template <typename T>
class fibonacci{
private:
    T cache[91];  //한번 계산한 값을 저장하기 위함
    int n;
public:
    fibonacci(){
        memset(cache, -1, sizeof(T) * 91);    //배열의 모든 값을 -1로 setting
        cache[0] = 0;   //F0
        cache[1] = 1;   //F1
    }
    void setN(){
        cin >> n;
    }
    void solution(){
        if(n < 2){
            printIdx(n);
        }else{
            recursive(n);
            printIdx(n);
        }
    }
    T recursive(int n) {
        if (cache[n] > -1) return cache[n]; //이미 계산 되어있는 것 이면 바로 리턴
 
        cache[n] = recursive(n - 2) + recursive(n - 1);
        return cache[n];
    }
 
    void printIdx(int n) const{
        cout << cache[n] << endl;
    }
    void printAll() const{
        for(int i=0; i<91; i++)
            printf("[%d] -> %lld\n", i, cache[i]);
    }
};
 
int main(void){
    fibonacci<long long> fi;
    fi.setN();
    fi.solution();
    //fi.printAll();
    return 0;
}

4. 인증

문제 출처 : https://www.acmicpc.net/problem/2748

감사합니다.