[알고리즘/백준] 9009번 : 피보나치 (python)

미리 피보나치를 구해서 리스트에 저장 후 가장 큰 피보나치부터 가져와서 비교 후 원래 값에서 빼주는 형식으로 구현.

이제는 함수로 구현하려고 함...

def sol(n, fibo):
    answer = []
    if n == 0:
        return answer.append(0)
    for k in sorted(fibo, reverse=True):
        if k <= n:
            answer.append(k)
            n -= k
    return answer[::-1]


def get_fibo():
    fibo = [1, 2]
    while fibo[-1] <= 1000000000:
        fibo.append(fibo[-2] + fibo[-1])
    return fibo


if __name__ == '__main__':
    T = int(input())
    f = get_fibo()
    for i in range(T):
        result = sol(int(input()), f)
        print(*result)