C++ 그리디 알고리즘: 1부터 k까지 모든 숫자를 만들기 위해 배열에 추가해야 하는 최소 숫자 개수 구하기

문제 설명

숫자 배열 nums와 정수 k가 주어졌다고 가정해 보겠습니다. 우리는 nums에 최소한의 숫자를 삽입하여, [1, k] 범위 내의 어떤 숫자든 nums의 부분집합(원소들의 합)으로 표현할 수 있도록 만들어야 합니다.

예를 들어 입력이 nums = [3, 5], k = 6이라면 출력은 2가 됩니다. 1과 2를 삽입하면 다음과 같이 1부터 6까지의 모든 숫자를 만들 수 있기 때문입니다.

1 = [1]
2 = [2]
3 = [3]
4 = [1, 3]
5 = [5]
6 = [1, 5]

접근 방법

이 문제는 그리디(Greedy) 알고리즘으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

현재까지 [1, sum] 범위의 모든 숫자를 만들 수 있다고 가정하면, 다음으로 확인할 숫자는 sum + 1입니다. 정렬된 배열에서 다음 원소 i가 sum + 1 이하라면, 기존 부분집합에 i를 더하는 방식으로 커버 범위를 [1, sum + i]까지 확장할 수 있습니다. 반면 i가 sum + 1보다 크다면 sum + 1은 절대 만들 수 없으므로, sum + 1을 직접 삽입해야 합니다. 이렇게 하면 커버 범위는 [1, 2 * sum + 1]로 두 배 가까이 확장됩니다.

알고리즘 단계

배열 nums를 오름차순으로 정렬합니다.
sum := 0, next := 1, ret := 0으로 초기화합니다.
nums의 각 원소 i에 대해 다음을 수행합니다.
- next < i인 동안 다음을 반복합니다.
  - sum >= k이면 루프를 빠져나갑니다.
  - sum := sum + next
  - next := sum + 1
  - ret을 1 증가시킵니다.
- sum >= k이면 루프를 빠져나갑니다.
- sum := sum + i
- next := sum + 1
next <= k인 동안 다음을 반복합니다.
- sum := sum + next
- next := sum + 1
- ret을 1 증가시킵니다.
ret을 반환합니다.

C++ 구현 예제

아래 구현 예제를 통해 동작 방식을 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;

class Solution {
   public:
   int solve(vector<int>& nums, int k) {
      sort(nums.begin(), nums.end());
      int sum = 0;
      int next = 1;
      int ret = 0;
      for (int i : nums) {
         while (next < i) {
            if (sum >= k) break;
            sum += next;
            next = sum + 1;
            ret++;
         }
         if (sum >= k) break;
         sum += i;
         next = sum + 1;
      }
      while (next <= k) {
         sum += next;
         next = sum + 1;
         ret++;
      }
      return ret;
   }
};

int solve(vector<int>& nums, int k) {
   return (new Solution())->solve(nums, k);
}

int main(){
   vector<int> v = {3, 5};
   int k = 6;
   cout << solve(v, k);
}

입력

[3, 5], 6

출력

복잡도 분석

배열 정렬에 O(n log n), 이후의 순회 과정에서 각 원소와 삽입되는 숫자를 한 번씩만 처리하므로 전체 시간 복잡도는 O(n log n + log k)입니다. 공간 복잡도는 O(1)로, 추가적인 자료구조 없이 상수 공간만 사용합니다.