백준 1003번, 피보나치 함수

백준 1003번 c++ 문제풀이

문제:

백준 1003

풀이:

1. 문제에 재귀로 되어있는 피보나치 함수의 코드가 주어져있지만, 재귀로 풀 시 시간이 너무 오래 걸릴 거 같아 dp를 이용했다.
2. 다행히도 입력 값이 40까지로 정해져있다.
3. dp는 이전의 값을 미리 저장해놔서 함수를 할 때 마다 반복할 필요 없이 값을 바로바로 불러다가 쓸 수 있다는 장점이 있다.
4. 주어진 재귀 코드에 0, 1이 호출 될 때마다 프린트 되는 0, 1의개수를 세어야하는데, 0과 1이 호출되는 횟수를 미리 저장해놓는다.
5. fib0[a], fib1[a]의 값을 fib[a]의 0과 1이 프린트 되는 개수라고 했을 때.

6. for(int i=2;i<=a;i++){ fib0[i] = fib0[i-1] + fib0[i-2]; fib1[i] = fib1[i-1] + fib1[i-2]; }

위 코드와 같이 값을 저장해준다.

1. 출력한다.

코드:

#include <iostream>
#include <algorithm>
#include <map>


using namespace std;

void fibcount(int a){
    
    int fib0[a+1];
    int fib1[a+1];

    fib1[0] = 0;
    fib1[1] = 1;

    fib0[0] = 1;
    fib0[1] = 0;
    
    for(int i=2;i<=a;i++){
        fib0[i] = fib0[i-1] + fib0[i-2];
        fib1[i] = fib1[i-1] + fib1[i-2];
    }
    cout << fib0[a] << " " << fib1[a] << "\n";
}

int main(void){

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;

    cin >> t;

    for(int i=0;i<t;i++){
        int input;

        cin >> input;

        fibcount(input);
    }

    return 0;   
}   

감사합니다.