백준 1003 - 피보나치 함수

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

1003번: 피보나치 함수

문제 풀이

---

 

피보나치 3번째를 호출하면 다음과 같은 일이 일어난다. 이때 피보나치 3번째는 피보나치 2번째 1번째를 호출하는 식의 재귀형식으로 호출이 진행될때 최종으로 만들어지는 0과 1의 개수를 구하는 문제이다.

 

 

접근 방법

---

처음 접근 방법은 피보나치 수열 N번째를 재귀를 통해 분해하는 방법을 사용했으나 시간초과가 발생했다. 

다음 방법은 0, 1의 개수 또한 피보나치 수열을 만족하기 때문에 0번째, 1번째의 0, 1의 개수를 설정하고 피보나치 함수를 이용했다. 

 

 

코드 

---

#include <iostream>
#include <cstdlib>
using namespace std;
int testcase;
int num1[41],num0[41];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin>>testcase;
    num0[0]=1;num1[0]=0;
    num0[1]=0;num1[1]=1;
    while(testcase--){
        int n;cin>>n;
        for(int i=2;i<=n;i++){
            num0[i]=num0[i-1]+num0[i-2];
            num1[i]=num1[i-1]+num1[i-2];
        }
        cout<<num0[n]<<" "<<num1[n]<<"\n";
    }
    return 0;    
}

funny algorithm 0.0!