[LeetCode] 1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

https://leetcode.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/

Find the Minimum Number of Fibonacci Numbers Whose Sum Is K - LeetCode

Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

 

 

k는 피보나치 수열의 수들의 합으로 나타낼 수 있다.

이 때 이 수들의 최소개수를 구하는 문제다.

이 문제도 간단하다.

먼저 k 보다 작거나 같은 범위에서 피보나치 수열을 만들어준다. (k가 10^9이므로 통상 50정도면 충분하다.)

 

그 후, 이 수열을 쭉 훑으면서 k보다 작거나 같은 최대값을 골라준후,

k에서 빼준값으로 k를 업데이트 해주며, 횟수를 ++ 해준다.

k가 0이 될떄까지 이를 반복한다.

 

k보다 작은 최대값들로만 더해도 된다고?

이것이 가능한 이유를 간단하게 알아보면, 피보나치의 수열은 특성이 큰 수는 작은 수들의 합으로 무조건 나타낼 수 있다는 것이다. 따라서 작은 수들의 합은 큰 수의 합으로 바꿀 수가 있다. 특히 k를 만들기 위해 작은 수들로만 더한다면 이 작은 수들로 k에 가장가까운 수 역시 만들 수 있기 때문에 k에 가장 가까운 수들로 정해주면 된다.

 

전체 풀이 코드

 

class Solution {
public:
    int findMinFibonacciNumbers(int k) {
        vector<long> fib = {1,1};
        int idx = 0, ret = 0;
        for (int i=0; fib.back()<=k; i++) fib.push_back(fib[i] + fib[i+1]);
        for (; k>0; ret++) {
            while (fib[idx]<=k) idx++;
            k-=fib[idx-1];
            idx = 0;
        }
        return ret;
    }
};