29. UVa-12455 Bars //Making subset using Bitmask-method

문제

<그림1: 문제설명>

문제는 간단하게. t개의 case가 주어졌을 때 각 case별로 p개의 정수로 된 list가 주어진다. 이 때 list의 부분집합 중 그 합이 n이 되는 경우가 존재하는가? 

이 문제를 부분집합 합(subset sum)이라 부르는 경우도 있는데, 기본적으로 all possible subset을 보는 것이 optimal한 문제라고 한다. 이 때 모든 subset을 봐야하는데, 이것을 bit계산으로 매우 빠르게 할 수 있어서 그 방법을 소개한다.

#include<iostream>
using namespace std;

int main() {
	int n,t,p, sum,possible;
	int list[1000];	//n<=1000 in problem
	cin >> t;	//number of test case
	while (t--) {
		possible = false;	//possibility of subset sum==n
		cin >> n;	//length of the bar we want to contain
		cin >> p;	//the number of bars we have
		for (int l = 0; l < p; l++) cin >> list[l];	//input part
		for (int i = 0; i < (1 << p); i++) {	//the number of possible subset is 2^p 
			sum = 0;
			//j-loop: loop that calculate sum of i'th subset
			for (int j = 0; j < p; j++) {	//bit 1 to j(correspond to element of input set)
				if (i & (1 << j)) {	//test whether jth bit on
					sum += list[j];	//if jth bit on, then list[j] is in i'th subset
				}
			}
			if (sum == n) {	//this subset's sum == n
				possible = true;
				break;	//now can terminate searching
			}
		}
		cout << ((possible) ? "YES" : "NO") << endl;

	}

	return 0;
}

bit연산이 무지 빨라서 2100만번 정도의 연산이 0.1초 안에 가능하다. 2^n에 비례하는 sol을 가질 수 밖에 없는 subset문제에 대해서는 bitmask기법을 이용하는게 좋을 것 같다.