[1182] 부분수열의 합

알고리즘 분류	비트 마스크
solved.ac 티어	silver 3
문제 링크	https://www.acmicpc.net/problem/14889
관련 블로그 포스팅

이 게시글은 코드 플러스 강의 '알고리즘 기초 2/2'의 강의 내용을 기반으로 작성되었습니다.

문제 이해

N 개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분 수열 중에서 그 수열의 원소를 모두 더한 값이 S가 되는 경우의 수를 구하는 문제. 즉,

1. 공집합을 제외한 부분 수열을 구해야 하고
2. 부분 수열의 원소를 더한 값이 S가 되는지 확인해야 한다.

 

---

문제 접근

N 개의 정수로 이루어진 수열에서  부분 수열 구하기

수열의 부분 수열은 각 원소의 유무로 표현이 가능하다.

수열의 n 번째 원소를 An이라고 했을 때, 부분 수열을 아래와 같이 표현할 수 있다.

A1	A2	A3	...	An
O	O	O	...	O
X	X	X	...	X

즉, 가능한 부분 수열의 개수(경우의 수)는 아래와 같다. $$2^n$$ 

이때, 문제의 조건에서 n은 20보다 크거나 같으므로 가능한 부분 수열의 개수가 2^32(int 범위)보다 작아 비트 마스크로 해당 문제를 풀 수 있다는 것을 알 수 있다.

 

---

문제 풀이

해당 문제는 비트 마스크로 접근 가능하므로 편의상 수열을 집합으로 바꿔 표현하겠다.

 

부분 집합 구하기

비트 마스크를 사용하면 전체 집합 S는 (1 << N) - 1로 표현 가능하다. 즉, S의 부분 집합은 0부터 (1 << N) -1까지의 정수로 표현 가능하다.

n = 5인 수열을 가정할 때, 
n의 부분 집합은 0부터 (1 << n) - 1 (2^n - 1)의 정수로 표현될 수 있으므로
부분 집합은 0부터 31까지의 정수로 아래와 같이 표현된다.

0 = 00000(2)       -> 공집합
1 = 00001(2)       -> {a1}
2 = 00010(2)       -> {a2}
3 = 00011(2)       -> {a1, a2}
...
31 = 11111(2)     -> {a1, a2, a3, a4, a5}

 

따라서 부분 집합을 만드는 코드는 1 부터 (1 << n) - 1 의 정수를 만드는 것으로 짤 수 있다. (1부터인 이유는 공집합 제외이므로)

for (int i = 1; i < (1 << n); i++) {	//부분 집합을 만든 것.
		
}

 

각 부분 집합의 원소의 합 구하기

부분 집합을 비트 마스크로 표현했으므로, 전체 집합 S의 n 번째 요소가 부분 집합에 있는지 확인하는 것이 쉬워졌다.

검사 연산 S & (1 << N)을 이용하면 된다. 따라서 부분 집합의 원소의 합을 구하는 코드는 아래와 같이 짤 수 있다.

for (int k = 0; k < n; k++) {
		// 부분수열(i)에서 전체 집합 S의 k번째 원소가 있는지 확인
		if (i & (1 << k)) {
        	//있다면 합을 구한다.
			sum += a[k];
		}
}

 

---

전체 코드

#include <iostream>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>

using namespace std;

int main() {
	int n = 0;
	int s = 0;

	int sum = 0;	//특정 부분수열의 합
	int cnt = 0;	// 조건을 만족하는 부분수열의 개수

	cin >> n >> s;

	vector<int> a(n);

	//원본 수열 받기
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	//부분수열의 합 구하기
	for (int i = 1; i < (1 << n); i++) {	// 부분수열을 만든 것.
		sum = 0;

		for (int k = 0; k < n; k++) {
			// 부분수열에서 k번째 원소가 있는지 확인
			if (i & (1 << k)) {
				sum += a[k];
			}
		}

		//합이 s와 같으면 개수 + 1
		if (sum == s) {
			cnt += 1;
		}
	}

	cout << cnt;


	return 0;
}