[백준] 9009번 피보나치

💡문제접근

• 테스트케이스에서 주어진 수보다 작은 가장 큰 피보나치 수를 단계적으로 빼주면서 0이 될 때까지 계산을 수행한다.
• 문제에서 주어지는 각 테스트 데이터의 최댓값은 1,000,000,000으로 1,000,000,000보다 작으면서 피보나치 수열 중에서 나올 수 있는 최댓값은 701,408,733으로 44번째 항이 된다. 따라서 45번째 항까지의 피보나치 수열을 구해놓은 다음 그리디 알고리즘에 따라 계산을 해주면 된다.

💡코드(메모리 : 31256KB, 시간 : 56ms)

import sys
input = sys.stdin.readline

T = int(input().strip())
fibonacci = [1, 1, 2, 3]
for i in range(4, 45):
    fibonacci.append(fibonacci[i-2] + fibonacci[i-1])

for i in range(T):
    n = int(input().strip())
    li = []
    for i in range(44, -1, -1):
        if n == 0:
            break
        if fibonacci[i] <= n:
            n -= fibonacci[i]
            li.append(fibonacci[i])
    print(*reversed(li), sep=" ")

💡소요시간 : 7m