[백준] 14225번 부분수열의 합 (비트마스크)

링크

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

14225번: 부분수열의 합

풀이

수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 문제이다.

 

일단 비트 마스크를 이용하여 수열 S의 모든 부분 수열의 합을 구하고 map에 추가하고

모든 부분 수열을 구하고 나서 1부터 최대로 나올 수 있는 2000000까지 map에 존재하는지 확인하여

존재하지 않다면 값을 출력하도록 하였습니다.

 

#include<iostream>
#include<map>

using namespace std;

int arr[1 << 22];
map<int, bool> _map;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[1 << i];
	}

	for (int i = 1; i < (1 << N); i++) {
		int sum = 0;
		for (int j = 0; (1 << j) <= i; j++) {
			if (i & (1 << j)) {
				sum += arr[1 << j];
			}
		}
		_map[sum] = true;
	}


	for (int i = 1; i <= 2000000; i++) {
		if (_map[i] != true) {
			cout << i;
			break;
		}
	}
	return 0;
}