https://www.acmicpc.net/problem/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()
'알고리즘💻 > 그리디' 카테고리의 다른 글
BOJ 1439번: 뒤집기 (1) | 2023.09.14 |
---|---|
BOJ 11501번: 주식 (0) | 2023.09.13 |
BOJ 18921번: Cost of Subtree (0) | 2021.08.18 |
BOJ 2450번: 모양 정돈 (0) | 2021.08.04 |
BOJ 2457번: 공주님의 정원 (0) | 2021.08.04 |