[BOJ] 1003번. 피보나치 함수.cpp

#. Problem

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

* The copyright in this matter is in BOJ

#. 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. 

#. Code

Code 1) 

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

#include <iostream>   using namespace std;   int tc, N, p0, p1;   int fibonacci(int n) {     if (n == 0) {         p0++; return 0;     }     else if (n == 1) {         p1++; return 1;     }     else {         return fibonacci(n - 1) + fibonacci(n - 2);     } }   int main() {     ios::sync_with_stdio(false);     cin >> tc;       while (tc--) {         cin >> N;         p0 = 0; p1 = 0;           fibonacci(N);         cout << p0 << ' ' << p1<<'\n';     }     return 0; } Colored by Color Scripter

cs

- 기본적인 생각대로 해결했을 경우이다. 당연히 시간 초과..

Code 2) 

#include <iostream>
 
using namespace std;
 
int tc, N;
int fb[42] = {1};
 
int main() {
    ios::sync_with_stdio(false);
    cin >> tc;
 
    for (int i = 2; i < 42; i++) {
        fb[i] = fb[i - 1] + fb[i - 2];
    }
 
    while (tc--) {
        cin >> N;
        
        cout << fb[N] << ' ' << fb[N+1] << '\n';
    }
 
    return 0;
}

#. Result

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

3

0

1

3

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

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

1 0

0 1

1 2

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