[LeetCode] 330. Patching Array

https://leetcode.com/problems/patching-array/description/

leetcode - Patching Array

문제 유형 : 그리디

문제 난이도 : Hard

 

문제

Given a sorted integer array nums and an integer n, add/patch elements to the array such that any number in the range [1, n] inclusive can be formed by the sum of some elements in the array.

Return the minimum number of patches required.

 

정수 배열 nums와 정수 n이 주어진다. 배열에 요소를 추가하여 닫힌구간 [1, n]의 모든 수를 표현할 수 있도록 만드시오.

표현은 배열의 부분집합의 합으로 한다고 가정합니다.

 

풀이

https://leetcode.com/problems/patching-array/solutions/5319434/easy-to-understand-greedy-approach-detailed-explanation/

의 도움을 받았다..

 

아이디어를 거의 떠올렸는데, 구현에서 막혀 도움을 받았다.

 

우리가 필요한 수 miss라는 변수를 만든다. 1부터 시작한다. miss의 값은 [1, miss]까지는 만들 수 있음을 의미한다.

그리디한 측면으로 따졌을 때, 작은 수를 가진 요소부터 추가하는 것이 좋다.

더 많은 부분집합들을 만들 수 있고, 특히 1, 2와같은 수는 필수적임을 알 수 있다.

 

만약 miss가 이번 nums의 요소보다 크거나 같다면, miss에 nums[i]를 누적시킨다. 만들 수 있는 수의 범위를 확장한다.

만약 miss가 nums[i]보다 이번에 작다면, miss를 nums에추가해야 한다. (패치 추가). 횟수를 누적시키고, miss에 miss를 더해 만들 수 있는 수의 범위를 확장한다.

 

코드

C++

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        long long miss = 1;
        int i = 0;
        int ans = 0;

        while(miss <= n) {
            if(i < nums.size() && nums[i] <= miss) {
                miss += nums[i];
                i++;
            } else {
                miss += miss;
                ans++;
            }
        }

        return ans;
    }
};