#1003번 피보나치 함수 (C++)

처음 이 문제를 풀때는 재귀를 통해 풀었다. 

#include <iostream>
using namespace std;

int zero=0;
int one=0; 

void calculate (int x){
    if(x==0) {zero++; return;}
    else if(x==1) {one++; return;}
    return calculate(x-2), calculate(x-1);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    for(int i=0; i<n; i++){
        int num = 0;
        cin >> num;
        calculate(num);
        cout << zero << " " << one;
        zero = 0; one = 0;
    }
    
    return 0;
}

모든 테스트 케이스는 통과했으나, 정답률의 20%를 채울 무렵 시간초과가 떠버렸다. 

 

무언가 규칙이 있게거니 싶어 샘플 데이타를 구해봤다. 

출력값 / 입력값	1의 갯수	0의 갯수
5	5	3
4	3	2
3	2	1
2	1	1
1	1	0
0	0	1

1의 갯수와 0의 갯수가 나타내는 교집합을 만들어보자면

Fibo(x) 0의 갯수 = Fibo(x-2)의 0과 1의 합 = Fibo (x-2)

FIbo(x) 1의 갯수 = Fibo(x-1)의 0과 1의 합 = Fibo (x-1)이 나오는 것을 알 수 있다. 

그렇다면 0과 1의 갯수의 합으로 이루어진 배열을 구한 뒤, Fibo(x-2)와 Fibo(x-1)을 구하면 된다.

 

#include <iostream>
using namespace std;

int ans[91]={1,1,};

int calculate(int x){
    if(x<=1) return ans[x];
    else{
        if(ans[x]>0) return ans[x]; //조건을 삽입하지 않으면 초기화 된 값 '0'을 바로 출력해버림 
    }
    return ans[x] = calculate(x-1) + calculate(x-2);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    for(int i=0; i<n; i++){
        int num = 0;
        cin >> num;
        if(num==0) cout << "1 0" << "\n";
        else if(num==1) cout << "0 1" << "\n";
        else{
            calculate(num);
            cout << ans[num-2] << " " << ans[num-1] << "\n";
            }
    }
    
    return 0;
}

검사 시간이 고작 0ms밖에 안든다.