[백준 14225] 부분수열의 합, C++

https://www.acmicpc.net/problem/14225

14225번: 부분수열의 합

본 문제는 주어진 수열의 부분수열을 구하고 구한 부분수열의 합을 구하는 문제다.
문제를 해결하기 위해 2가지의 과정이 필요하다.
1. 모든 부분수열의 합을 구한다.
2. 1.에서 구만 합을 저장한다.

위의 과정마다 각각 2가지 방법이 떠올랐다.

1.을 해결하기 위해서는 비트 마스크를 이용하여 모든 경우의 수를 찾는 방법과 재귀 함수를 이용하여 수열을 선택하는 방법
2.를 해결하기 위해서 합을 구하고 vector에 저장 및 중복 제거, bool 배열을 이용하여 true, false를 저장하는 방법

결과적으로 재귀함수를 이용하면서 bool 배열을 사용하는 방법이 내가 생각한 방법 중 가장 빠른 연산 속도가 나왔다.

#include <cstdio>
 
using namespace std;
 
int n;
int d[21];
bool chk[2000001];
 
void cal(int index, int sum) {
  
  // 모든 수열을 선택하였을 때  
  if (index == n) {
      
    // 구한 부분수열의 합 true로 변경
    chk[sum] = true;
    return;
  }
   
  // 수열 선택
  cal(index+1, sum + d[index]);
  cal(index+1, sum);
}
 
int main() {
  scanf("%d", &n);
  
  for (int i = 0; i < n; i++) {
    scanf("%d", &d[i]);
  }
  
  cal(0, 0);
  
  // 답 찾기
  int index = 1;
  while (true) {
    if (!chk[index]) {
      printf("%d\n", index);
      return 0;
    }
    else index += 1;
  }
}

다음은 비트마스크를 이용하고 vector의 중복값을 제거하는 소스코드다.

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int d[21];
 
int main() {
  int n;
  scanf("%d", &n);
  
  for (int i = 0; i < n; i++) {
    scanf("%d", &d[i]);
  }
  
  /*
    000 = 0
    001 = 1
    010 = 2
    011 = 3
    100 = 4
    101 = 5
    110 = 6
    111 = 7
  */
  
  vector<int> v;
  for (int i = 1; i < (1<<n); i++) {
    int sum = 0;
    int brute = i;
    for (int j = 0; j < n; j++) {
      int dir = brute % 2;
      brute /= 2;
      if (dir) {
        sum += d[j];
      }
    }
    v.push_back(sum);
  }
  sort(v.begin(), v.end());
  
  v.erase(unique(v.begin(), v.end()), v.end());
  
  int ans = 1;
  for (int i = 0; i < v.size(); i++) {
    if (v[i] != ans) {
      printf("%d\n", ans);
      return 0;
    }
    ans += 1;
  }
  printf("%d\n", ans);
}