문제

수열 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가지 경우로 나눠서 재귀를 돌린다.