Jin의 일상

문제 설명

1. 1부터 1,000,000,000 까지의 범위를 갖는 n이 주어집니다.

2. 피보나치 수열을 최소의 개수로 더해서 n을 만들었을 때 결과를 리턴해야 합니다.

알고리즘

1. 주어진 범위 내에서 가능한 피보나치 수열을 리스트에 담습니다. (1 ≤ n ≤ 1,000,000,000)

2. 이분 탐색 알고리즘을 통해 n보다 작거나 같은 수를 찾습니다. 

3. n에서 찾은 수를 빼줍니다. 

4. n이 0이 될 때 까지 2~3번 과정을 반복합니다.

코드

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

fibo = [0, 1]
idx = 0
while fibo[idx + 1] < 1000000000:
    fibo.append(fibo[idx] + fibo[idx + 1])
    idx += 1

t = int(input())
for _ in range(t):
    n = int(input())
    stack = []
    lt = 0
    rt = len(fibo) - 2
    while n != 0:
        while lt <= rt:
            mid = (lt + rt) // 2
            if fibo[mid] > n:
                rt = mid - 1
            else:
                lt = mid + 1
        n -= fibo[rt]
        stack.append(fibo[rt])
        lt = 0
    stack.reverse()
    print(*stack)