bitmask_sumation of subsequence_14225

백준 조합의 14225번 문제 부분수열의 합을 비트마스크로 풀이해보도록 하겠습니다.

문제 URL : https://www.acmicpc.net/problem/14225

1182번에서 조금만 변형해서 해결할 수 있었습니다.
1182 풀이 보러가기

2000001로 둔 이유는 n이 20개까지 들어올 수 있으며, 100000이 최대숫자였기때문에 다 더했을때 나올 수 있는 최대 수와 연관지어 크게 잡은 것이 이유입니다.

Source Code :

#include<iostream>
#include<vector>
/*#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>*/

// #define SIZE 1010

using namespace std;

// typedef long long int ll;
int flags[2000001] = { 0, };

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	/* declare variables */
	int n;
	vector <int> arr;

	/* input */
	cin >> n;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		
		arr.push_back(tmp);
	}

	/* process */
	for (int i = 1; i < (1 << n); i++) {
		vector <int> v;
		// i = 00001
		// 00010
		// 00011
		// ...
		// 11111
		for (int j = 0; (1 << j) <= i; j++) {
			// j = 00001
			// 00010
			// 00011
			// ...
			// 11111
			if (i & (1 << j)) {
				v.push_back(j);	// [4] or [3] or [2] or [1] or [0]
			}
		}

		int sum = 0;
		for (int j = 0; j < v.size(); j++) {
			sum += arr[v[j]];
		}
		//if (sum == S) {
		//	count++;
		//}
		flags[sum] = 1;
	}

	for (int i = 1; i < 20000001; i++) {
		if (flags[i] == 0) {
			cout << i << endl;
			break;
		}
	}

	// cin >> n;
	return 0;
}

개인이 공부하고 포스팅하는 블로그입니다. 작성한 글 중 오류나 틀린 부분이 있을 경우 과감한 지적 환영합니다!