이 문제에서는 하나의 수 K가 주어지며, 우리의 목표는 합이 K와 같아지는 최소한의 피보나치 항의 개수를 구하는 것입니다.
피보나치 수열은 앞의 두 수를 더하여 다음 수를 만들어 가는 수열입니다. 피보나치 수열은 두 개의 초기값 F0과 F1에서 시작하며, 초기값은 각각 0과 1 또는 1과 1로 정할 수 있습니다.
피보나치 수열은 다음과 같습니다.
0 1 1 2 3 5 8 13 ...
문제 이해를 위한 예시
입력
K = 5
출력
2
설명: 합 5는 피보나치 수인 3과 2를 더하여 만들 수 있으며, 이때 사용되는 항의 개수는 2개입니다.
해결 접근 방법
피보나치 수열에는 1이 포함되어 있기 때문에, 어떤 수든 피보나치 수들의 합으로 표현할 수 있습니다. 예를 들어 1을 n번 더하면 합이 n이 됩니다. 하지만 우리의 과제는 합을 만들 때 사용하는 피보나치 항의 개수를 최소화하는 것입니다.
이 문제는 동전 교환(Coin Change) 문제에서 착안하여 해결할 수 있습니다. 동전의 가치가 모두 피보나치 수라고 생각하면 되는데, 이때 사용되는 알고리즘 기법을 프로그래밍에서는 그리디(Greedy) 접근법이라고 부릅니다.
먼저 합 n보다 작거나 같은 피보나치 수들을 모두 구합니다. 그다음 마지막 항부터 시작하여 n에서 해당 항을 뺄 수 있는 만큼 반복해서 빼면서, 동시에 사용된 항의 개수를 증가시킵니다. n이 현재 항보다 작아지면, n보다 작거나 같은 바로 앞의 피보나치 항으로 이동하여 같은 과정을 반복합니다. 마지막에 누적된 항의 개수를 출력하면 됩니다.
알고리즘
피보나치 항을 계산하는 함수를 생성합니다.
n보다 작거나 같은 모든 피보나치 항을 계산합니다.
다음 항이 n보다 크면 벡터에 추가하지 않고 함수를 종료합니다.
합이 n이 되는 최소 피보나치 항의 개수를 구하는 함수를 생성합니다.
피보나치 항을 저장할 벡터를 초기화합니다.
합 n이 0보다 클 때까지 피보나치 항을 빼는 과정을 반복합니다.
합 n을 j번째 피보나치 항으로 나누어 해당 항이 합에 기여하는 횟수를 구합니다.
구해진 항의 개수를 출력합니다.
예제 코드
아래는 위 해결 방법의 동작을 보여주는 C++ 프로그램입니다.
#include <bits/stdc++.h>
using namespace std;
void findFiboTerms(vector<int>& fiboVals, int K){
int i = 3, nextTerm;
fiboVals.push_back(0);
fiboVals.push_back(1);
fiboVals.push_back(1);
while (1) {
nextTerm = fiboVals[i - 1] + fiboVals[i - 2];
if (nextTerm > K)
return;
fiboVals.push_back(nextTerm);
i++;
}
}
int findTermForSum(int K){
vector<int> fiboVals;
findFiboTerms(fiboVals, K);
int termCount = 0, j = fiboVals.size() - 1;
while (K > 0) {
termCount += (K / fiboVals[j]);
K %= (fiboVals[j]);
j--;
}
return termCount;
}
int main(){
int K = 11;
cout<<"합이 K와 같은 최소 피보나치 항의 개수: "<<findTermForSum(K);
return 0;
}출력 결과
합이 K와 같은 최소 피보나치 항의 개수: 2
위 예제에서 K = 11일 때, 11은 8과 3 두 개의 피보나치 수로 표현할 수 있으므로 최소 항의 개수는 2가 됩니다.