[BAEKJOON] 2748번. 피보나치 수 2

#. Problem

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

* The copyright in this matter is in BAEKJOON

피보나치 수는 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번째 피보나치 수를 구하는 프로그램을 작성하시오.

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

    - 재귀함수

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 재구함수를 사용

     fibo(n)= fibo(n-1) + fibo(n-2)

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

#include <iostream>   using namespace std;   int N; long long fb[91];   int main() {     // Improving iostream performance     ios::sync_with_stdio(false);     cin >> N;       fb[1] = 1;     for (int i = 2; i <= N; i++) {         fb[i] = fb[i - 1] + fb[i - 2]; ;    }       cout << fb[N];       return 0; } Colored by Color Scripter

cs

- 피보나치 수열을 코딩하라고 하면 거의(?) 재귀함수를 사용해서 해결했기 때문에,

  당연시 재귀함수로 문제에 접근했지만.. 동적 계획법으로 분류된 문제인만큼 재귀함수는 시간 초과로 실패하고 말았다..

  

  배열을 사용하여 접근할 경우 time complexity는 O(n)이 나오고,

  재귀함수를 사용할 경우 O(2^n)이 나오므로 input이 90이 주어질 경우 시간을 초과할 수 밖에 없었던 것 같다.

#. Result

  - Input --------------------------------------------------------

10

------------------------------------------------------------------

  - Output --------------------------------------------------------

55

------------------------------------------------------------------

#. Others code

#include <iostream>
 
using namespace std;
 
int main() {
    long long a, b, c, n;
    cin >> n;
 
    a = 0; b = 1; c = 1;
    while (--n) {
        c = a + b;
        a = b;
        b = c;
    }
    cout << c;
}