문제 이해하기
배열 nums와 하나의 숫자 n이 주어졌다고 가정해 봅시다. 배열에 요소를 몇 개 추가하여 [1, n] 범위(양 끝값 포함) 안의 모든 숫자를 배열 요소들의 합으로 표현할 수 있도록 만들어야 합니다. 이때 추가해야 하는 최소한의 요소 개수, 즉 '패치(patch)'의 수를 구하는 것이 문제입니다.
예를 들어 배열이 [1, 4]이고 n = 7일 때를 살펴보겠습니다. 처음에는 부분합으로 1, 4, 5만 만들 수 있습니다. 하지만 여기에 2를 추가하면 배열은 [1, 2, 4]가 되고, 각 부분집합의 합은 1, 2, 3, 4, 5, 6, 7이 되어 [1, 7] 범위의 모든 숫자를 표현할 수 있게 됩니다. 따라서 정답은 1입니다.
접근 방법
이 문제는 그리디(Greedy) 알고리즘으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
req는 현재까지 만들 수 있는 연속 범위의 다음 값을 의미합니다. 즉, [1, req-1] 사이의 모든 숫자를 이미 만들 수 있다는 뜻입니다.현재 요소
nums[i]가req보다 작거나 같다면, 기존 범위에 이 요소를 활용해 커버 가능한 범위를req + nums[i]까지 확장할 수 있습니다.반대로
nums[i]가req보다 크거나 배열을 모두 사용했다면, 값req자체를 새로 추가해야 합니다. 이렇게 하면 커버 범위가 두 배로 늘어나고(req × 2), 패치 개수가 1 증가합니다.
알고리즘 단계
req = 1,i = 0,ret = 0으로 초기화합니다.req <= n인 동안 다음을 반복합니다.i가 배열 크기보다 작고nums[i] <= req라면,req += nums[i]를 수행하고i를 1 증가시킵니다.그렇지 않다면
req += req(범위 두 배 확장)를 수행하고ret을 1 증가시킵니다.
반복이 끝나면
ret을 반환합니다.
C++ 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다. 참고로 req를 long long int로 선언한 이유는 범위가 계속 두 배씩 늘어날 때 오버플로우를 방지하기 위해서입니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minPatches(vector<int>& nums, int n) {
long long int req = 1;
int i = 0;
int ret = 0;
while(req <= n){
if(i < nums.size() && nums[i] <= req){
req += nums[i];
i++;
} else {
req += req;
ret++;
}
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1,4};
cout << (ob.minPatches(v, 7));
}입력
{1,4}출력
1
복잡도 분석
시간 복잡도는 O(m + log n)입니다. 여기서 m은 배열의 길이이며, 패치를 추가할 때마다 커버 범위가 두 배씩 늘어나기 때문에 반복 횟수가 log n으로 제한됩니다. 공간 복잡도는 O(1)로, 추가적인 메모리가 거의 필요하지 않습니다.