[백준] 1003번 피보나치함수

 

0이 출력되는갯수, 1이 출력되는갯수를 구해라.

fibo(3) 의 경우 fibo(2) 와 fibo(1)로 나뉜다. fibo(2) 의 출력갯수와 fibo(1)의 출력갯수의 합만큼 출력한다.

fibo(4) 또한 fibo(3)와 fibo(2)로 나뉘며 결국 fibo(3)의 출력갯수와 fibo(2)의 출력갯수의 합만큼 출력된다.

 

단순히 0에대한 피보나치 1에대한 피보나치만 구해주면 되는문제이다. 의외로 정답률이 낮다..

#include <iostream>
#include <vector>
#include <cmath>

typedef long long big_int;
void getfiboCount(big_int n, big_int& out0, big_int& out1){

    if (n == 0){
        out0 = 1;
        out1 = 0;
    }else if (n == 1){
        out0 = 0;
        out1 = 1;
    }else{
        big_int last[2] = {1,0};
        big_int now[2] = {0,1};
        big_int temp[2] = {0, 0};
        
        for(int i=1; i<n; ++i){
            for(int j=0;j<2;++j){
                temp[j] = now[j];
                now[j] += last[j];
                last[j] = temp[j];
            }
        }
        out0 = now[0];
        out1 = now[1];
    }
}
int main(void){
    big_int n = 0;
    int t = 0;
    std::cin >> t;
    for(int i=0; i<t; ++i){
        std::cin >> n;

        big_int ans1 = 0;
        big_int ans2 = 0;
        getfiboCount(n, ans1, ans2);
        std::cout << ans1 << " " << ans2 << "\n";
    }
}

 

그냥 단순하게 반복문을 돌면서 풀었다.