[백준] 9009번: 피보나치 (Python, 파이썬)

문제 링크: https://www.acmicpc.net/problem/9009

9009번: 피보나치

내가 푼 방법:

- 피보나치 수가 n보다 크거나 같을 때까지만 loop를 돌린다. (dp에 작은 수 부터 저장됨)

- 그 다음 저장된 피보나치 수를 역순으로 (큰 순서대로) 확인해가면서, 제일 큰 피보나치 수를 n에서 빼주고, 그 다음 사용할 피보나치 수를 찾는다. (반복)

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    dp = [0, 1]
    res = []
    n = int(input())

    i = 2
    while True:
        fibo_i = dp[i-1] + dp[i-2]
        dp.append(fibo_i)
        if fibo_i >= n:
            break
        i += 1

    for i in dp[::-1]:
        if i == 0:
            break
        if i <= n:
            res.append(i)
            n -= i 
    
    for i in res[::-1]:
        print(i, end=' ')