문제
수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오.
예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다. baekjoon
코드
#include <iostream>
#include <vector>
using namespace std;
vector<bool> checked(20 * 100000 + 1);
void get_min(vector<int> v, int idx, int sum) {
sum += v[idx];
checked[sum] = true;
if (idx + 1 < v.size()) {
get_min(v, idx + 1, sum);
get_min(v, idx + 1, sum - v[idx]);
}
}
int main() {
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) cin >> v[i];
get_min(v, 0, 0);
for (int i = 1; i < checked.size(); i++) {
if (!checked[i]) {
cout << i;
break;
}
}
}
풀이
현재 idx에 위치한 값을 포함하거나 안하는 2가지 경우로 나눠서 재귀를 돌린다.