[BOJ/PYTHON] 9009. 피보나치

백준 문제 링크: https://www.acmicpc.net/problem/9009

문제 요약

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

핵심 아이디어 및 풀이

피보나치 리스트를 먼저 구하고 시작하면 된다. 이때, 입력이 최대 1,000,000,000이기에 피보나치를 50번째까지 구해줬다. (사실 50번째까지 안 가도 되는데 0으로 딱 끝내려고 이렇게 했다)

최소 개수가 되려면 그리디하게 제일 큰 값부터 넣어보면 되기에 피보나치 리스트를 큰 값부터 내림차순으로 정렬한다.

피보나치 리스트를 순서대로 돌면서 입력값보다 피보나치가 딱 작아지는 순간부터를 answer list에 append해줬다. 그리고 append한 수만큼을 입력값에서 빼 다음 피보나치를 구하면 된다.

피보나치 수열을 큰 것부터 거꾸로 봤기 때문에 출력 시에는 다시 뒤집어서 출력하면 된다. 피보나치 수열이 원래 점점 커지는 형태이기에 정렬해줬다.

풀이

# silver1-9009. 피보나치

import sys
input = sys.stdin.readline

# 최소 개수 되려면 제일 큰 값부터 넣어보면 됨

fibonacci = [0]*50
fibonacci[0] = 0
fibonacci[1] = 1
for i in range(2, 50):
    fibonacci[i] = fibonacci[i-1] + fibonacci[i-2]
fibonacci.sort(reverse=True)

t = int(input()) 
for _ in range(t):
    num = int(input()) 
    answer_list = []
    for fibo_num in fibonacci:
        if fibo_num <= num and num != 0: # num이 0이 아닌 한도 내에서 가장 큰 피보나치 수
            answer_list.append(fibo_num)
            num -= fibo_num
    print(*sorted(answer_list))

 

실행 시간

메모리 31256KB, 시간 52ms (python3)