[Python] BOJ/백준 9009번 피보나치

[문제]

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

9009번: 피보나치

 

[풀이]

우선 피보나치 리스트를 만들어 올바른 값을 미리 넣어준다.

문제에 n의 최댓값이 1,000,000,000이라고 했기 때문에 44번 째 피보나치 수열까지만 구하면 된다. 

 

만들 수 있는 숫자 중 최소 개수로 n을 만들기 위해서는 n 이하의 수 중 가장 n과 가까운 수를 써야 한다.

문제에 나온 예시처럼 100을 만들기 위해서는 (3 + 8 + 89) 도 가능하지만 (3 + 8 + 34 + 55) 도 가능하기 때문에 34 + 55 인 수인 89를 사용하는 것이 더 적은 개수를 사용한 것이 된다.

 

그러므로 넉넉하게 46부터 시작해 100보다 같거나 작은 수가 나왔을 때 해당 수를 result 리스트에 넣고 n에서 해당 수를 빼 n이 0이 될때까지 반복하면 최소 개수를 만들 수 있다.

 

최소수의 피보나치 수들을 증가하는 순서로 출력해야 하기 때문에 sort() 함수를 이용해 정렬한 다음 출력하면 된다.

 

 

[코드]

import sys

fibo = [0, 1]
for i in range(2, 47):
    fibo.append(fibo[i-1] + fibo[i-2])

for _ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    result = []
    while n:
        for k in range(46, 1, -1):
            if fibo[k] <= n:
                number = fibo[k]
                n -= number
                result.append(number)
                break

    result.sort()
    for i in result:
        print(i, end=' ')
    print()