백준 1003번 C++

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

1003번: 피보나치 함수

이번 문제에서 처음에 피보나치를 재귀로 풀었을 때의 C++코드를 줘서

어...? 왜 친절하지라고 생각을 하고 그 함수 그대로 사용해서 코드를 다음과 같이 만들었습니다.

당연하게도 밑에 코드는 실패한 코드입니다.

#include <iostream>

using namespace std;

int zeroCount = 0, oneCount = 0;

int fibonacci(int n) {
    if (n == 0) {
        zeroCount++;
        return 0;
    }
    else if (n == 1) {
        oneCount++;
        return 1;
    }
    else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

int main() 
{
    int testCase;
    cin >> testCase;

    for (int i = 0; i < testCase; i++) {
        zeroCount = 0; oneCount = 0;
        int a;
        cin >> a;
        fibonacci(a);
        cout <<zeroCount << " " << oneCount <<"\n";
    }
}

 

이와 같이 코드를 만드니 시간초과가 떴습니다.

솔직히 이걸로 성공할 것이라고 생각은 하지 않긴 했습니다.

저는 DP로 풀어볼까 생각을 했습니다. 물론 좋은 방식이지만 제가 아직 DP에 적응이 되어 있지 않은 상태라서

찾아봐야하는데 쉬운 문제에 그렇게 하기에는 자존심이 좀.. 상했습니다.

그래서 for문으로 최대 n의 값이 40까지기 때문에 배열 안에

미리 0이 몇번 나오는지 그리고 1이 몇번 나오는지 저장을 해두고 testCase에 대해서 출력을 하도록 코딩을 했습니다.

 

#include <iostream>
#include<algorithm>
#include<vector>

using namespace std;

int fibonach[41][2] = { 0, };

int main() 
{
    fibonach[0][0] = 1; fibonach[1][0] = 0;
    fibonach[0][1] = 0; fibonach[1][1] = 1;

    for (int i = 2; i < 42; i++) {
        fibonach[i][0] = fibonach[i - 2][0] + fibonach[i - 1][0];
        fibonach[i][1] = fibonach[i - 2][1] + fibonach[i - 1][1];
    }


    int testCase;
    cin >> testCase;

    for (int i = 0; i < testCase; i++) {
        int a;
        cin >> a;
        cout << fibonach[a][0] << " " << fibonach[a][1] << "\n";
    }
}

이 방식으로 문제를 제출하니 바로 성공하였습니다.