C++에서 합이 K인 피보나치 수의 최소 수 찾기

<시간/>

수 k가 있다고 가정하고 피보나치 수를 여러 번 사용할 수 있는지 여부에 관계없이 합이 k와 같은 피보나치 수의 최소 수를 찾아야 합니다.

따라서 입력이 k =7과 같으면 피보나치 수와 같이 출력은 2가 됩니다. 1, 1, 2, 3, 5, 8, 13, ... k =7의 경우 2 + 5 =7.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

배열 정의 f
f
끝에 0 삽입
f
끝에 1 삽입
f <=k의 마지막 요소인 동안 −
- f
  에 삽입(f의 마지막 요소 + f의 두 번째 마지막 요소)
ret :=0
j :=f의 마지막 인덱스
동안 (j>=0 및 k> 0), 수행 -
- f[j] <=k이면 -
  - k :=k - f[j]
  - (ret 1 증가)
- 그렇지 않으면
  - (j를 1만큼 감소)
리턴 렛

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#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));
}