백준 9009번 피보나치(Python, C++)

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

9009번: 피보나치

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

결론적으로 사용하는 피보나치 수가 최소 개수가 되려면 n보다 같거나 작은 피보나치 수 중 가장 큰 피보나치 수를 사용하고, 이를 반복하면 된다. 가령 n=100이면 89를 사용하고, 남은 11에 대해서 8을 사용하고, 또 남은 3에 대해 3을 사용하면 된다.

100 = 3 + 8 + 89

 

왜 이렇게 될까? 

최대한 적은 갯수가 되려면 예를 들어 34+55 대신 89로 써야한다. 

 

1) 만약 89대신 55를 사용한다면 어떻게 될까?

100 = 55 + 34 + 8 + 3 이 되는데 이때 55+34는 89이므로 89 + 8 + 3이 더 적은 갯수가 된다.

 

2) 89과 55 둘 다 사용하지 않는다면?

1부터 34까지 피보나치 수를 다 더해도 89가 되지 못하므로 100을 만들 수 없다.

 

그러므로 100보다 같거나 작은 피보나치 수를 고르고 또 남은 수보다 같거나 작은 피보나치 수를 고르는 과정을 0이 될때까지 반복하면 최소 갯수를 만들 수 있다.

 

 

문제를 보면 n이 최대 1,000,000,000 까지 가능하다고 했다. 그럼 몇번 때 피보나치 수까지 가능한걸까?

다음 코드를 통해 알아보자

 

<Python>

f = [0,1]
for i in range(2, 47):
    c = f[i-2]+f[i-1]
    f.append(f[i-2]+f[i-1]) 
for j in range(47):
    print(j,"번 째: ",f[j])

0 번 째:  0
1 번 째:  1
2 번 째:  1
3 번 째:  2
4 번 째:  3
5 번 째:  5
6 번 째:  8
7 번 째:  13
8 번 째:  21
9 번 째:  34
10 번 째:  55
11 번 째:  89
12 번 째:  144
13 번 째:  233
14 번 째:  377
15 번 째:  610
16 번 째:  987
17 번 째:  1597
18 번 째:  2584
19 번 째:  4181
20 번 째:  6765
21 번 째:  10946
22 번 째:  17711
23 번 째:  28657
24 번 째:  46368
25 번 째:  75025
26 번 째:  121393
27 번 째:  196418
28 번 째:  317811
29 번 째:  514229
30 번 째:  832040
31 번 째:  1346269
32 번 째:  2178309
33 번 째:  3524578
34 번 째:  5702887
35 번 째:  9227465
36 번 째:  14930352
37 번 째:  24157817
38 번 째:  39088169
39 번 째:  63245986
40 번 째:  102334155
41 번 째:  165580141
42 번 째:  267914296
43 번 째:  433494437
44 번 째:  701408733
45 번 째:  1134903170
46 번 째:  1836311903

 n이 최대 1,000,000,000 까지 가능하므로 44번째까지 쓸 수 있다. 하지만 문제에서는 각자 다른 수를 써야한다고 했으므로 배열을 편의상 1부터 넣어서 1,2,3,... 이런 식으로 만든다면 46번째까지 쓸 수 있다. 

그럼 이제 문제를 풀어보자

 

<Python>

p = [1,2]
for i in range(2, 46):
    p.append(p[i-2]+p[i-1]) 
T = int(input())

for j in range(T):
    n = int(input())
    result=[]
    while(n):
        for k in range(46):
            if(p[k]<=n):
                t = p[k]
        n -= t
        result.append(t)
        result.sort()
    for b in range(len(result)):
        print(result[b], end=' ')

 

 

<C++>

#include <iostream>
#include <vector>
using namespace std;

int main(){
	int T;
    int f[46] = {1,2};
    for(int i=2; i<46; i++){
    	f[i] = f[i-1] + f[i-2];
    }
    cin >> T;
    while(T--){
    	int n, t;
        cin >> n;
        vector<int> result;
        for(int j=45; j>=0; j--){
        	if(f[j]<=n){
            	n -= f[j];
                result.push_back(f[j]);
            }
        }
        for(int k=result.size() - 1; k >= 0; k--){
        	cout << result[k] << ' ';
        }
        cout << '\n';
    }
    return 0;
}