BitMasking_sumation of subsequences_1182
백준 조합 브루트포스의 1182번 문제 부분수열의 합을 비트마스크로 풀이해보도록 하겠습니다.
문제 URL : https://www.acmicpc.net/problem/1182
이 문제는 조합 응용 브루트포스로 분류된다고 써있지만 저는 비트마스크를 이용하여 문제 해결에 접근했습니다.
전수 조사 시 v에는 인덱스가 거꾸로 저장됨으로서 arr의 원소에 접근하게 되는 것이 핵심입니다.
4 3 2 1 0 …idx
0 0 0 0 1
0 0 0 1 0
0 0 0 1 1
.
.
1 1 1 1 1
1로 세팅된 자리 즉 인덱스를 v는 기억하는 것이지요
0 1 2 3 4 …idx
-7 -3 -2 5 8
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 main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
/* declare variables */
int n, S, count = 0;
vector <int> arr;
/* input */
cin >> n >> S;
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++;
}
}
cout << count << endl;
// cin >> n;
return 0;
}
개인이 공부하고 포스팅하는 블로그입니다. 작성한 글 중 오류나 틀린 부분이 있을 경우 과감한 지적 환영합니다!