[BOJ] 1182. 부분수열의 합

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

비트마스크를 이용해서 모든 경우를 구해볼 수 있다.

 

문제의 예제 테스트 케이스를 이용해보면

5 0

-7 -3 -2 5 8

예제의 입력이 위와 같다.

 

 

 index : 4   3   2  1  0

 원소  : -7  -3  -2  5  8

00000 부터 11111( (1 << n) -1)까지의 경우를 모두 해주는데 각 자리의 숫자는 선택할 원소의 index라고 볼 수 있다.

예를 들어, 00101의 경우는 -2와 8을 선택한 경우라고 할 수 있다.

 

 

1을 포함하고 있는 자리(해당 자리의 원소를 선하는 경우)를 확인하기 위해서는 &연산을 사용하면 된다.

 

위의 00101과 1 << 2  (100)를 &연산을 해주면 00100 이 나와서 0이 아닌값(4)가 나오므로 2번째 자리에 1이 있는 것을 확인할 수 있고 마찬가지로 1 << 0 을해서 0번째자리에 1이 있는 것을 확인할 수 있다.

 

반대로 00101과 1<<3 (1000)을 &연산을 해주면 00000 이 나와서 0이 되므로 3번째 자리에 1이 없다는 것을 확인할 수 있따. 

 

이런식으로 각 자리에 1이 있으면 그 자리의 원소값을 sum에 더하고 

각자리의 확인을 마친뒤에는 sum이 s와 같은지 검사해주면된다.

 

#include <iostream>
using namespace std;
 
 
int n, s, ans;
int num[20];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n >> s;
 
    for (int i = 0; i < n; i++) {
        cin >> num[i];
    }
 
 
    for (int i = 1; i < (1 << n); i++) {
 
        int sum = 0;
        for (int j = 0; j < n; j++) {
            //j번째 자리수가 1을 가지고 있다.(수열의 j번째 원소를 선택하는 경우)
            if ((i & (1 << j)) != 0) {
                sum += num[j];
            }
        }
 
 
        //다 더한 값이 s
        if (sum == s) {
            ans++;
        }
    }
 
    cout << ans << '\n';
 
    return 0;
}