[백준] 1003번

저번 문제에 이어서 풀었다. 직접 피보나치 수를 따라가서 규칙을 찾았다. 즉

​

fibonacci(0)의 호출 횟수는 fibonacci(n-1)과 같았고,

fibonacci(1)의 호출 횟수는 fibonacci(n)과 같았다.

​

그러므로 fibonacci 값을 40까지 구한 후에

​

출력하면 되는 것이다.

​

#include <iostream>
using namespace std;

void fibo(int num){
    int dp[41];
    dp[0]=0;
    dp[1]=1;
    int i;
    for(i=2;i<41;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    cout<<dp[num-1]<<" "<<dp[num]<<endl;
    
}
int main(){
    int testcase,i,num;
    cin>>testcase;
    for(i=0;i<testcase;i++){
        cin>>num;
        if(num>40 || num<0)
            return 0;
        if(num==0){
            cout<<1<<" "<<0<<endl;
            continue;
        
    }
        if(num==1){
            cout<<0<<" "<<1<<endl;
            continue;
        }
        fibo(num);

}

return 0;
}