BOJ 1003 - 피보나치 함수 (C++)

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

피보나치 함수에서 생성되는 함수값이 아니라, 매 n에서 0과 1이 몇 번 리턴되는 지를 구하는 문제라고 생각했다.
따라서 다음과 같이 n이 0일 때부터 40일 때까지의 0과 1의 개수를 구해 배열에 저장하고, 필요한 n이 입력으로 들어오면 그 배열의 값을 꺼내서 출력하는 방식으로 구현했다. 이렇게 구현하면, 처음 계산을 제외하고는 크게 시간이 소요되지 않기 때문에 0.25초라는 시간 제한으로부터 자유로워진다.

코드 :

#include <iostream>
#include <vector>

using namespace std;
typedef pair<int, int> pi;

vector<pi> fi(41, {0, 0});

void setFibonacci() {
    fi[0] = {1, 0};
    fi[1] = {0, 1};
    
    for (int i = 2; i <= 40; i++) {
        fi[i] = {fi[i-1].first + fi[i-2].first, fi[i-1].second + fi[i-2].second};
    }
    
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int t, n;
    cin >> t;
    setFibonacci();
    
    while (t--) {
        cin >> n;
        cout << fi[n].first << ' ' << fi[n].second << '\n';
    }
}

---

하지만, 실제로는 n마다 0과 1의 개수를 나열해보면, 그 순서가 피보나치 수열과 동일하다는 사실을 다른 사람들의 풀이를 보고 뒤늦게 알 수 있었다.

즉,

0 : 1 0 1 1 2 3 ... -> n = 1에서부터 시작되는 피보나치 수열
1 : 0 1 1 2 3 5 ... -> n = 0에서부터 시작되는 피보나치 수열

다음과 같이 해석할 수 있는 것이다.

사실 문제에서 주어진 피보나치 수열을 구하는 코드는 탑 다운 형식이었는데, 그 코드를 가지고 어떻게 0의 개수와 1의 개수를 동시에 담을 지 가늠이 안 잡혔고, 또 막상 구현해보니 시간 초과가 떠서 바텀 업 형식으로 문제를 풀었다. 그 점이 문제에서 주어진 조건을 제대로 사용하지 않은 것 같아, 정답을 얻은 후에도 굉장히 찜찜한 기분이 들었다.

하지만 위와 같은 규칙이 있다는 것을 알고, 역시 주어진 조건을 사용하는 방법이 있었다는 것을 알게 되었다. 주어진 그대로 문제를 해석하는 것도 좋지만, 수열을 직접 손으로 구해보는 것처럼 이것저것 시도해보고, 주어진 조건을 모두 사용하기 위해 노력해야겠다.

새로운 해석 + top-down을 적용해 수정한 코드 :

#include <iostream>

using namespace std;

int fi[41] = {0};

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

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t, n;
    cin >> t;

    while (t--) {
        cin >> n;
        if (n == 0) {
            cout << 1;
        } else {
            cout << fibonacci(n-1);
        }
        cout << ' ' << fibonacci(n) << '\n';
    }
}