119일 (1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K) greedy, memoization

Given an integer k, return the minimum number of Fibonacci numbers whose sum is equal to k. The same Fibonacci number can be used multiple times.

The Fibonacci numbers are defined as:

• F1 = 1
• F2 = 1
• Fn = Fn-1 + Fn-2 for n > 2.

It is guaranteed that for the given constraints we can always find such Fibonacci numbers that sum up to k.

 

Example 1:

Input: k = 7
Output: 2 
Explanation: The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, ... 
For k = 7 we can use 2 + 5 = 7.

Example 2:

Input: k = 10
Output: 2 
Explanation: For k = 10 we can use 2 + 8 = 10.

Example 3:

Input: k = 19
Output: 3 
Explanation: For k = 19 we can use 1 + 5 + 13 = 19.

 

Constraints:

• 1 <= k <= 10^9

 

 

- 접근방법

1. fibonacci(i) <= k < fibonacci(i+1) 일때 fibonacci(i)를 구한다.

 

2. fibonacci(i)부터 fibonacci(1)까지 수들의 합이 k가 되는 경우, k가 되는 피보나치 수열의 개수(answer)를 구한다.

 

+ 피보나치 수열을 매번 새로 구하지않고 한번 구하였던 값을 기억하기 위해 자료구조 Map을 이용하여 메모이제이션을 활용하였다.

 

 

 

- 코드

class Solution {
    private static Map<Integer, Integer> map = new HashMap<>();

    public int findMinFibonacciNumbers(int k) {
        int answer = 0;
        int temp = 0;
        int i = 0;

        while (true) { // 1
            temp = fibonacci(++i);

            if (temp > k) {
                break;
            }
        }

        temp = 0;

        while (temp != k) { // 2

            if (temp + map.get(i) <= k) {
                temp += map.get(i);
                answer++;
            }
            i--;
        }

        return answer;
    }

    private int fibonacci(int i) {
        if (map.containsKey(i)) return map.get(i);

        int result;

        if (i > 2) {
            result = fibonacci(i - 1) + fibonacci(i - 2);
            map.put(i, result);

        } else {
            result = 1;
            map.put(i, result);
        }

        return result;

    }

}

 

접근방법은 간단하지만, 메모이제이션 활용을 하지 않는다면 시간초과가 된다는 점. 그리고

k보다 같거나 작은 피보나치 수열들의 일부의 합은 무조건 k가 될 수 밖에 없다는 점도 기억해야한다.(테스트케이스가 통과되려면 무조건 답은 존재)

 

 

 

 

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

LeetCode - The World's Leading Online Programming Learning Platform