백준 1182 부분수열의 합 (비트마스크)

앞서 풀어본 1182번 문제를 비트마스크를 이용해 푼다.

명심해야 할 핵심은 부분집합을 '하나의 수'로 나타낸다는 개념이다.

 

{1, 3, 5}를  101010 로 나타내어 42라는 하나의 수로 나타내는 것이다.(2^1 + 2^3 + 2^5 = 42)

집합의 원소 값을 이진수의 자리수로 생각하는 것이다.

즉, 42 = {1, 3, 5} 이다.

 

해당 문제에서는 집합을 '하나의 수'로 보는 같은 개념을 사용하지만 원소 값 자체를 인덱스로 사용하진 않는다.

 

n이 주어지면 집합에 있는 원소의 개수는 n개가 된다. 이는 '하나의 수'로 치환될 수 있는데, n자리 수의 이진수로 표현할 수 있다. 따라서 모든 부분 집합은 0~(1 << n) - 1의 범위로 나타낼 수 있다.

공집합은 { }이고, 0으로 나타낸다.

만약 주어진 집합의 원소가 5개라면 {x, x, x, x, x}로 나타낼 수 있고, 이를 이진수로 보면 11111라 할 수 있다.

11111은 31이고, (1 << 5)는 32이다.

따라서 주어진 집합의 원소가 5개라면 가능한 부분 집합은 0 ~ (1 << 5) - 1의 범위를 가지는 것이다.

그리고 만약 첫 번째 원소만을 갖는 부분집합이 있다면 이는 이진수 10000(16)으로 나타낼 수 있다.

따라서 아래 코드에서 i의 값 자체가 하나의 집합(부분 집합)을 나타낸다고 생각하면 된다.

 

그리고 k의 값을 주어진 원소의 개수만큼 증가시키면서 몇 번째 자리의 원소를 가지는지 check하며(11723 문제 참조), 해당 되는 원소가 있을 경우 sum으로 더해서 부분 집합의 합을 구한다.

 

집합이든 부분집합이든 집합을 '하나의 수'로 생각한다는 개념을 가지고 있어야 풀 수 있는 문제였다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
 
int main(int argc, char** argv) {
    int n, s, ans = 0;
    scanf("%d %d", &n, &s);
 
    vector<int> v(n);
    for (int i = 0; i < n; i++)scanf("%d", &v[i]);
 
    //1<<n으로 하는 이유는 집합을 { x, x, x, x }라 했을 때 각 위치를 이진수의 위치와 같다고 생각하기 위함이다.
    //만약 주어진 집합의 원소의 개수가 5개라고 한다면 { x, x, x, x, x }와 같을 것이다.
    //(1 << 5)는 32이고 이진수로 나타내면 100000이다. 따라서 (1 << 5) - 1은 31이고 이진수로 나타내면 11111이다.
    //이 이진수를 원소의 집합과 matching시킨다면 이진수의 자리수가 1비트이면 해당 원소값을 가지는 것이고, 0이면 해당 원소값을 가지지 않는 것이라 할 수 있다.
    //따라서 i값을 (1 << n) - 1까지 돌려보는 것은 모든 부분집합을 살펴보는 것이라 할 수 있다.
    //i가 16이 되면 10000이고 이는 집합의 첫 번째 원소만을 가지는 부분집합이다.
    //공집합은 포함하지 않으므로 i는 1부터 시작한다.
    for (int i = 1; i < (1 << n); i++) {
        //k는 0부터 시작하여 n - 1까지 가면서 해당 부분집합(i의 값 자체가 부분집합임)이 어떤 index의 원소를 가지고 있는 확인한다.
        int sum = 0;
        for (int k = 0; k < n; k++) {
            //해당 부분집합에 들어있는 값을 더해준다.
            if (i & (1 << k)) {
                sum += v[k];
            }
        }
        if (sum == s) ans++;
    }
 
    printf("%d\n", ans);
 
    return 0;
}