백준 1003 - 피보나치 함수

문제 설명

fibonacci는 재귀로 풀어야한다는 것을 알아야한다. 

 

 

//0 : fibonacci(n-1)

//1 : fibonacci(n)

//fibonacci : fibonacci(n-1) + fibonacci(n-2)

 

0과 1의 개수는 위와 같은 식을 따른다. 
위의 식을 따라 알고리즘을 짜면 간단히 해결가능하다. 

*testcase를 배열로 주고서 풀 경우 문제가 생길 수 있다. testcase를 숫자로 받고서, 해당 값을 줄이면서 입력을 받으면서 푸는 것이 맞는 방법이다. 

 

#include <iostream>
using namespace std;

//0 : fibonacci(n-1)
//1 : fibonacci(n)
//fibonacci : fibonacci(n-1) + fibonacci(n-2)

int fibo[41];

int fibonacci(int n)
{
    if(n<=0)
    {
       fibo[0]=0;
        return 0;
    }
    else if(n==1)
    {
        fibo[1]=1;
        return 1;
    }
    if(fibo[n] !=0) return fibo[n];
    else{
        return fibo[n]=fibonacci(n-1) +fibonacci(n-2);
    }
}

int main() {
    int testCase;
    cin>>testCase;
    int n;
    for(; 0<testCase; testCase--)
    {
        cin>>n;
        if(n==0)cout<<1<< " "<<0<<'\n';
        else if(n==1)cout<<0<<" "<<1<<'\n';
        else{
        fibonacci(n);
        cout<<fibo[n-1]<<" "<<fibo[n]<<'\n';
        }
    }
    return 0;
}