[백준 / BOJ] 9009 피보나치

문제

출처 : www.acmicpc.net/problem/9009

9009번: 피보나치

N을 입력받았을때, 피보나치수들을 최소한으로 사용해서 N을 만들면 되는 문제다.

 

예를들어,

N = 100일때,

피보나치수 3 8 89

 

풀이

피보나치수들을 최소한의 수로 조합해서 N을 만들어야 하기 때문에, N에서 가능한 가장 큰 피보나치수 부터 빼가면서 출력하면 된다.

 

피보나치수는 0 1 1 2 3 5 8 13 21 34 55 89 144... 이렇게 늘어나고,

 

100의 경우

144 는 100보다 크니 100보다 작거나 같은수중 가장큰 피보나치수인 89부터 시작한다.

1. 100에서 89를 빼면 11이 된다.

11보다 작거나 같은 피보나치수중 가장 큰 값은 8 이다.

2. 11에서 8을 빼면 3이다.

3보다 작거나 같은 피보나치수중 가장 큰 값은 3 이다.

3. 3에서 3을 빼면 0이다.

 

따라서 답은 3 8 89가 된다.

위를 반복하면 정답이되는데, 

 

위 알고리즘?이 항상 성립하는지 볼려면,

N에서 N보다 작거나 같으면서 가장큰 피보나치 수 fibo(a) 를 뺐을때 나온수 N - fibo(a)가 N - fibo(a)보다 작거나 같으면서 가장큰 피보나치 수들로 뺏을때 항상 0이 나오는지 보면 된다.

위 말을 다르게 풀어쓰면, 모든 N이 (N > 0) 피보나치수들의 합으로 표현될수있는지 보면되는데, 문제에서 "양의 정수는 하나 혹은 그 이상의 서로 다른 피보나치 수들의 합으로 나타낼 수 있다" 라고 주어졌으므로, 항상 성립하는것을 알수있다.

소스코드

https://github.com/devxb/JJUNalgo/blob/master/9009%20%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98/main.cpp

devxb/JJUNalgo