[BOJ 9009, Python 3] 피보나치

https://www.acmicpc.net/problem/9009

9009번: 피보나치

 

풀이

N보다 작거나 같은 가장 큰 피보나치 수를 계속 빼주면 된다. 

 

 

N보다 작거나 같은 가장 큰 피보나치 수를 빼지 않는다고 해보자

만약 pibo[i]값을 빼야하는데 다른 값을 빼야한다면 pibo[i] = pibo[i-1]+pibo[i-2]이므로 피보나치 수 1개로 빼야할 것을 2개로 빼야해서 최소 개수를 구하라는 문제의 답이 될 수 없다.

그리고 만약 N = 21이라면 21 = 13 + 8로 구할 수 있지만, 20= 8 + 5 + 3 + 2 + 1 + 1로 서로 다른 피보나치 수들의 합으로 답을 구할 수 없다는 문제점도 생긴다.

 

 

코드

for _ in range(int(input())):
    n = int(input())
    ans = []
    while n != 0:
        arr = [0, 1]
        while arr[1] <= n:
            arr = arr[1], sum(arr)
        if arr[1] == n:
            ans.append(arr[1])
            n -= arr[1]
        else:
            ans.append(arr[0])
            n -= arr[0]
    print(' '.join(map(str, sorted(ans))))