<알고리즘 문제풀이&연습>/[C++] 백준

[백준 2748] 피보나치 수2

사용자 BlockDMask 2017. 12. 5. 15:36
반응형
  • 안녕하세요. 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. 소스 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//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, -1sizeof(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] > -1return 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;
}
cs


4. 인증



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

감사합니다.

반응형

'<알고리즘 문제풀이&연습> > [C++] 백준' 카테고리의 다른 글

[백준 1463] 1로 만들기 (BFS)  (0) 2017.12.13
[백준 1463] 1로 만들기 (DP)  (2) 2017.12.12
[백준 2748] 피보나치 수2  (0) 2017.12.05
[백준 1924] 2007년  (0) 2017.12.04
[백준 5648] 역원소 정렬  (0) 2017.11.29
[백준 1212] 8진수 2진수  (1) 2017.11.28
[백준 2447] 별찍기10  (1) 2017.11.22
[백준 2446] 별찍기9  (0) 2017.11.21
[백준 10820] 문자열 분석  (0) 2017.11.21