백준 9009, 피보나치

개요

문제 링크
실버 1, Greedy
n을 최소 개수의 피보나치 수의 합으로 나타내기

---

접근

1. 우선 쟁점은 모든 n이 피보나치 수의 합으로 만들어질 수 있는가? 이다. 문제에서는 맞다고 하고 넘어갔는데 이해가 안됐다.
2. {서로 다른 피보나치 수의 합의 집합} = 자연수 임을 확인한다.
   귀납법이랑 이런저런 방법을 해보다가 막혀서 질문 게시판에 올라온 제켄도르프의 정리에 대해 읽어봤다. 역시 이런 걸 보면 구해보고 싶은 마음은 다들 비슷한가보다. 방법은 결국 귀납법이었다.

1) n = 1 일때는 반드시 된다.

n = 1 -> {1}

2) n = k 까지가 모두 된다고 가정하고 n = k+1에 대해 가능한지 확인하자.

n = k -> set(k)
n = k+1 = 피보나치수 -> {fib(i)}
n = k+1 != 피보나치수 -> {fib(i), set(n-fib(i))}
// fib(i) = n보다 작은 최대 피보나치수

n-fib(i) < k 임이 자명하므로 1~k까지 구성이 가능하다면 k+1도 구성이 가능하다. 이 내용은 chatGPT에 물어봐도 잘 알려준다.

3. 문제로 돌아와서, 모든 자연수가 피보나치 구성이 가능하므로 n-fib(i) 연산을 지속해주면 된다.

---

Pseudo code

while(n)
    fib = n보다작은최대피보나치수
    n -= fib
    출력목록.append(fib)

---

Source code

#include <bits/stdc++.h>
using namespace std;

const int N = 45;
vector <int> fib;
void test() {
    int n;
    cin >> n;
    vector <int> q;
    for (int i=N; i>=1; i--)
        if (fib[i] <= n) {
            q.push_back(fib[i]);
            n -= fib[i];
        }
    if (n)
        cout << n << " ";
    n = q.size();
    for (int i=0; i<n; i++)
        cout << q[n-1-i] << " ";
    cout << "\n";
}

int main() {
    fib.push_back(0);
    fib.push_back(1);
    for (int i=2; i<=N; i++)
        fib.push_back(fib[i-1]+fib[i-2]);
    int t;
    cin >> t;
    while(t--) test();
}