[Greedy] 백준 - 피보나치 9009번

피보나치 9009번

👌 문제 요약

피보나치 수들의 합이 주어진 정수와 같게 되는 최소 개수의 서로 다른 피보나치 수들을 구하라.

😜 key point

최소 개수의 서로 다른 피보나치 수들을 구하는 문제이므로 주어진 정수보다는 작지만 가장 큰 정수들을 골라 출력하면 되는 쉬운 문제 였다. (1,2,3, 과 같은 작은 수들이 많아 가능하였다.)

🤳 코드

n = int(input())

fib = [0,1]
for i in range(44):
    fib.append(fib[i]+fib[i+1])

fib.sort(reverse=True) # 반대로 뒤집기

def check(k):
    result = []
    for i in fib[0:-2]:
        if i <= k:         # 작은 값이 나오면 result 리스트에 넣는다.
            result.append(i)
            k -= i         
    
    return result

for _ in range(n):
    
    x = int(input())
    ans = check(x)
    ans.sort()
    
    print(*ans) # 리스트를 출력 가능(띄어쓰기 한 채로)