9009 - 피보나치

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

주어진 정수 X를 X와 같거나 가장 가까운 작은 수로 계속 빼면 된다.
마치 동전을 큰 단위부터 거슬러주면 제일 적은 개수로 거슬러 줄 수 있듯이,
가능한 큰 수로 계속 빼면 그것이 최소 개수로 표현할 수 있는 피보나치 수의 합이다.

ACM ICPC 2012 인터넷예선 D번 Fibonacci Numbers

#include <bits/stdc++.h>
using namespace std;

typedef long long lld;

vector<lld> fibo;

lld bound(vector<lld>& v, const lld& value){
    int l=0, r=v.size();
    while(l <= r){
        int mid=(l+r)/2;
        if(v[mid] <= value) l = mid+1;
        else r = mid-1;
    }
    return v[r];
}

vector<lld> trace;

void f(lld n){
    if(n <= 0){
        for(int i=trace.size()-1; i>=0; --i) printf("%lld ", trace[i]);
        puts("");
        return;
    }
    lld sel = bound(fibo, n);
    trace.push_back(sel);
    f(n - sel);
}

int main(){
    lld c=0, p=1;
    while(c <= 1e10){
        fibo.push_back(c);
        lld t = p;
        p = c + p;
        c = t;
    }
    
    int T;
    scanf("%d", &T);
    while(T--){
        lld n;
        scanf("%lld", &n);
        trace = {};
        f(n);
    }
    return 0;
}