비트마스크를 활용한 모든 부분집합의 검사(with 백준 1182)

문제링크 : https://www.acmicpc.net/problem/1182

풀이

이런 문제를 해결해야 할 때 가장 먼저 하게되는 고민은 어떻게 모든 부분집합을 검사하는가이다.

이 때 이런 고민을 쉽게 해결할 수 있게 해주는 것이 비트마스크를 활용하는 것이다.

위의 문제의 경우같이 원소가 5개인 집합의 부분집합을 모두 검사한다고 해보자

일단 만약 원소가 5개라면 부분집합의 총 가짓수는 2^5  인 32가지가 될 것이다.

(원소가 n개일 때 부분집합의 총 갯수는 2^n 이다.)

고로 변수 n에 원소의 갯수가 저장되어있다고 하면

0부터 1 << n 까지 검사를 하게된다.

그러니까 00000 ~ 11111 까지 검사를 하는것이다.

여기서 1의 위치가 원소의 위치와 같다고 생각하면된다.

이렇게 위의 수를 하나씩 검사할 때 그 안에서 다음의 로직을 수행한다.

for (int j = 0; j < n;j++)

{

if (i & (1 << j))

//원하는 처리

}

여기서 i는 00000 ~ 11111중 하나이다.

아무튼 이렇게 되면 i에 대해 1이 위치하고 있는 자리의 원소를 자신이 원하는 대로

처리해줄 수 있게되고 결과적으로 모든 부분수열에 대한 처리를 할 수 있다.

아래의 코드는 위의 문제에 대한 코드이며

여기서 j = 1 부터 시작하는 이유는 문제에서 공집합을 제외하기 때문이다.

#include <iostream>

using namespace std;

int arr[20];

int main()
{
	int n, s;
	int result = 0;
	scanf("%d %d", &n, &s);
	for (int i = 0; i < n; i++) scanf("%d", &arr[i]);

	for (int i = 1; i < (1 << n) ; i++)
	{
		int sum = 0;
		for (int j = 0; j < n;j++)
		{
			if (i & (1 << j))
				sum += arr[j];
		}
		if (sum == s)
			result++;
	}
	printf("%d\n", result);
}