[C++] 백준 9009번 - 피보나치

피보나치를 이용한 재귀 문제였다. 

Zeckendorf's theorem을 사용하는 문제였는데, 이분의 블로그를 보면 쉽게 이해가 가능하다.

결과적으로 피보나치 수가 n 보다 클 때 직전항을 빼주면서 재귀적으로 내려가면 된다. 

#include <iostream>
using namespace std;

long long fibo[10000001];

void solve(int n) {
    if (n == 0)
        return;

    for (int i = 0; i <= 10000000; i++) {
        if (n < fibo[i]) {
            solve(n - fibo[i - 1]);
            cout << fibo[i - 1] << " ";
            return;
        }
    }
    return;
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    int t, n;
    cin >> t;

    fibo[1] = 1;
    for (int i = 2; i <= 10000000; i++) {
        fibo[i] = fibo[i - 1] + fibo[i - 2];
    }

    while (t--) {
        cin >> n;
        solve(n);
        cout << endl;
    }

    return 0;
}