BOJ#9009

LEVEL :

Silver1

문제 요약 :

1 ≤ n ≤ 1,000,000,000 에 해당하는 자연수를 최소한의 피보나피수들의 조합으로 구성해라

해결 방안 :

1,000,000,000 이라는 수가 피보나치로 45번째 수보다 작았기에 1,000,000,000보다 작은 모든 피보나치들을 미리 배열로 구성시킨뒤, 주어진값에 가장 가깝지만 작은 수를 이진 탐색으로 구하여 temp 리스트에 집어 놓고, input 값에서 그 수를 뺀다. 위를 반복하면 최소의 수들의 조합을 만들 수 있다.

시간 복잡도 :

O(T{(Log45+a)+Nlog(N)}) = O(TNlogN)
N = len(temp)

Solution

import sys
input = sys.stdin.readline
if __name__ == "__main__" :
    fibo=[0,1]
    idx = 1
    while fibo[idx] <= 1000000000 :
        fibo.append(fibo[idx]+fibo[idx-1])
        idx+=1
    T = int(input().strip())
    arr = [int(input().strip()) for _ in range(T)]
    for each in arr :
        s = each
        start = 0
        finish = len(fibo)
        temp = []
        while s != 0 :
            mid = (start + finish)//2
            if fibo[mid] > s :
                finish=mid-1
                continue
            else :
                if fibo[mid] == s :
                    temp.append(fibo[mid])
                    s -= fibo[mid]
                else :
                    idx = mid
                    while idx <= finish :
                        if fibo[idx+1] > s or fibo[idx] == s  :
                            temp.append(fibo[idx])
                            s-=fibo[idx]
                            break
                        idx+=1      
        sorted_temp = sorted(temp)
        for val in sorted_temp :
            print(val,end=" ")
        print()