BOJ#9009

7227 ワード
greedy アルゴリズム#アルゴリズム# テキストリンク

LEVEL :
Silver1
質問の概要:
1≦n≦10000000の自然数は、最も少ない血宝または血獣からなる.
ソリューション:
10000000という数字はフィボナッチの45番目の数字なので、10000000未満のすべてのフィボナッチを予め並べておき、与えられた値に最も近いが小さい数のプローブで求め、templistに置いて入力値からその数字を減算します.上記を繰り返すと、最小数の組み合わせが生成されます.
時間の複雑さ:
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()
パッケージビューの作成
FTZ Level 8