문제 개요
하나의 수 k가 주어졌을 때, 그 합이 정확히 k가 되도록 하는 피보나치 수의 최소 개수를 구하는 문제입니다. 이때 같은 피보나치 수는 여러 번 재사용할 수 있다는 조건이 붙습니다.
예를 들어 k = 7이라고 가정해 보겠습니다. 피보나치 수열은 1, 1, 2, 3, 5, 8, 13, ... 과 같이 진행되므로, 7은 2 + 5로 표현할 수 있습니다. 따라서 필요한 피보나치 수의 최소 개수는 2개가 됩니다.
접근 방법: 탐욕(Greedy) 알고리즘
이 문제는 탐욕적(Greedy) 접근법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
항상 k 이하에서 가장 큰 피보나치 수를 선택하고, k에서 그 값을 뺍니다. 이 과정을 k가 0이 될 때까지 반복합니다.
피보나치 수열의 성질 덕분에 이 방법이 항상 최적해를 보장합니다.
알고리즘 단계별 설명
- 피보나치 수를 저장할 배열 f를 선언합니다.
- f에 0과 1을 초기값으로 삽입합니다.
- 배열의 마지막 원소가 k 이하인 동안, 마지막 두 원소의 합을 계속 추가하여 피보나치 수열을 생성합니다.
- 결과값 ret을 0으로, 인덱스 j를 배열의 마지막 위치로 초기화합니다.
- j가 0 이상이고 k가 0보다 큰 동안 다음을 반복합니다.
- f[j]가 k 이하라면, k에서 f[j]를 빼고 ret을 1 증가시킵니다.
- 그렇지 않다면 j를 1 감소시켜 더 작은 피보나치 수를 검사합니다.
- 반복이 끝나면 ret을 반환합니다.
C++ 코드 구현
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findMinFibonacciNumbers(int k) {
vector<int> f;
f.push_back(0);
f.push_back(1);
while (f.back() <= k) {
f.push_back(f[f.size() - 1] + f[f.size() - 2]);
}
int ret = 0;
int j = f.size() - 1;
while (j >= 0 && k > 0) {
if (f[j] <= k) {
k -= f[j];
ret++;
}
else
j--;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.findMinFibonacciNumbers(7));
}실행 결과 확인
입력
7
출력
2
동작 과정 상세 분석
k = 7일 때 알고리즘이 어떻게 동작하는지 살펴보겠습니다.
- 먼저 k 이하까지 피보나치 수열을 생성합니다: [0, 1, 1, 2, 3, 5, 8]
- 배열의 끝부터 탐색을 시작합니다. 8은 7보다 크므로 건너뜁니다.
- 5는 7 이하이므로 선택합니다 → 남은 값: 7 - 5 = 2, 사용 개수: 1
- 다음으로 3은 2보다 크므로 건너뜁니다.
- 2는 2 이하이므로 선택합니다 → 남은 값: 2 - 2 = 0, 사용 개수: 2
- k가 0이 되었으므로 종료하고 2를 반환합니다.
시간 복잡도
피보나치 수는 지수적으로 증가하기 때문에 k 이하의 피보나치 수는 약 O(log k)개밖에 존재하지 않습니다. 따라서 전체 시간 복잡도는 O(log k)로 매우 효율적입니다. 공간 복잡도 역시 피보나치 수열을 저장하는 데 O(log k)가 필요합니다.