C++에서 1부터 k까지의 모든 숫자를 생성하기 위해 몇 개의 숫자를 추가해야 하는지 계산하는 프로그램

num이라는 숫자 목록과 다른 값 k가 있다고 가정합니다. nums의 일부 하위 집합을 사용하여 [1, k]에서 임의의 수를 만들 수 있도록 nums에 삽입해야 하는 최소 수의 수를 찾아야 합니다.

따라서 입력이 nums =[3, 5], k =6과 같으면 출력은 2가 됩니다. 1, 2를 삽입해야 하므로 다음을 만들 수 있습니다. 1 =[1], 2 =[2 ], 3 =[3], 4 =[1, 3], 5 =[5], 6 =[1, 5].

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

• 배열 번호 정렬
• sum :=0, 다음 :=1, ret :=0
• 숫자에 있는 모든 i에 대해
  • 다음에
  • 합계>=k인 경우:
    • 루프에서 나오다
  • 합계 :=합 + 다음
  • 다음 :=합계 + 1
  • (ret 1 증가)
• 합계>=k인 경우:
  • 루프에서 나오다
• 합계 :=합 + i
• 다음 :=합계 + 1

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

#include
using namespace std;
class Solution {
   public:
   int solve(vector& 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& nums, int k) {
   return (new Solution())->solve(nums, k);
}

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

입력

[3, 5], 6

출력

2