1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K (합이 K인 피보나치 수의 최소 개수를 구하시오.)

정수 k가 주어지면 합이 k인 피보나치 수의 최소 개수를 반환합니다. 동일한 피보나치 수를 여러 번 사용할 수 있습니다. 피보나치 수는 다음과 같이 정의됩니다:

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

주어진 제약 조건에 대해 항상 최대 k의 합을 갖는 피보나치 수를 찾을 수 있다는 것이 보장됩니다.

예시 1:

입력: k = 7
출력: 2
설명: 피보나치 숫자는 다음과 같습니다: 1, 1, 2, 3, 5, 8, 13, ...
k = 7의 경우 2 + 5 = 7을 사용할 수 있습니다.

예시 2:

입력: k = 10
출력: 2
설명: k = 10의 경우 2 + 8 = 10을 사용할 수 있습니다.

예시 3:

입력: k = 19
출력: 3
설명: k = 19의 경우 1 + 5 + 13 = 19를 사용할 수 있습니다.

 

조건:

• 1 <= k <= 10⁹

 

정답:

public class Solution {
    public int FindMinFibonacciNumbers(int k) {
        List<int> result = new List<int>();
        List<int> fibonacchi = new List<int>();
        fibonacchi.Add(1);
        fibonacchi.Add(1);
        
        while (fibonacchi[fibonacchi.Count - 1] + fibonacchi[fibonacchi.Count - 2] <= k)
        {
            fibonacchi.Add(fibonacchi[fibonacchi.Count - 1] + fibonacchi[fibonacchi.Count - 2]);
        }

        while (k != 0)
        {
            result.Add(fibonacchi[fibonacchi.Count - 1]);
            k -= fibonacchi[fibonacchi.Count - 1];
            fibonacchi = fibonacchi.GetRange(0, fibonacchi.Count(n => n <= k));
        }

        return result.Count;
    }
}

해설: k보다 작은 숫자까지 피보나치 리스트를 생성합니다.

피보나치 리스트 내에서 가장 큰 수를 result에 추가하고 k에 해당 수를 빼주고 뺀 k값보다 같거나 작은 수만 남기도록 피보나치 리스트를 잘라줍니다. 

해당 작업을 k가 0이 될 때까지 반복하고 k가 0이 되면 result의 길이를 return합니다.