BOJ 9009번: 피보나치

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

9009번: 피보나치

하나의 양의 정수가 주어질 때, 피보나치 수들의 합이 주어진 정수와 같게 되는 최소 개수의 서로 다른 피보나치 수들을 구하라. 이때 피보나치 수는 증가하는 순서대로 출력

 

그리디 알고리즘이라는 것을 생각하고 규칙을 찾으면 간단하게 풀 수 있는 문제였다. 처음에는 피보나치라고 해서 dp를 사용해야 하나 했는데.. 다시 생각해보니 그럴 필요가 전혀 없었다.

피보나치 수를 생각해보면 f(n+1) = f(n) + f(n-1) 이기 때문에 결국 모든 피보나치 수는 피보나치 수의 합으로 이루어져 있는 것이다. 문제에서 피보나치 수의 합으로 표현할 수 없는 정수는 주어지지 않기 때문에 모두 피보나치 수의 합으로 표현할 수 있다고 가정하면, 주어진 정수 N보다 작거나 같은 수 중 제일 큰 수를 차례대로 빼면서 풀어나가면 답을 구할 수 있다.

 

피보나치 배열을 f[44]까지 구한 이유는 f[45]부터는 주어진 정수의 범위를 넘어가기 때문이다.

 

import sys
input = sys.stdin.readline

fib = [-1 for _ in range(45)]
fib[0] = 0
fib[1] = 1
for i in range(2, 45):
    fib[i] = fib[i-1] + fib[i-2]

T = int(input())
for _ in range(T):
    n = int(input())
    ans = []
    cnt = 0
    for i in range(44, -1, -1):
        if (fib[i] <= n):
            n -= fib[i]
            ans.append(fib[i])
            cnt += 1
            
        if (n==0):
            break
    for i in range(cnt-1, -1, -1):
        print(ans[i], end=" ")
    print()