피보나치[백준 9009]

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

 

 

최소의 숫자 개수로 입력받은 수를 만들어야 하니 가장 큰 수부터 배열을 확인하며 내려온다. 

n = int(input())
fibo = [0]*(50)
fibo[1] = 1 
fibo[2] = 1
for i in range(3, 50):    fibo[i] = fibo[i-1]+fibo[i-2]

def find(k):
    arr = []
    while k>0 : 
        i= 0 
        for i in range(50):
            if fibo[i]==k :
                arr.append(fibo[i])
                return arr 
            elif fibo[i] >k :
                arr.append(fibo[i-1])
                k-= fibo[i-1] 
                break
    return arr 
for _ in range(n):
    k = int(input())
    ans = find(k)
    ans.sort() 
    print(' '.join(map(str, ans)))
# print(ans)