[백준 1182번] [Bruteforce / 비트마스킹] 부분수열의 합

Approach

부분수열은 비트마스킹을 활용하여 쉽게 처리할 수 있다.

각각의 정수가 들어갈 지 안들어갈 지 선택할 수 있는 상황이므로, 총 가짓수는 $2^N$개이다.

잘 생각해보면, 0과 1을 활용핵서 들어갈 지 안들어갈 지 결정할 수 있고 이는 이진수를 활용해서 처리할 수 있다.

 

즉, N개의 정수를 활용해서 만들 수 있는 개수는 N개의 비트를 황룡해서 만들 수 있는 수와 완벽하게 동일하다.

따라서 1부터 $1 << N - 1$까지에 대해 합이 s가 되는 개수를 구해주면 된다.

 

상당히 배울 수 있는 점이 많은 내용이므로 자세한 것은 https://blog.naver.com/jinhan814/222579884777를 참고하도록 하자.

Theme 04. 완전 탐색(Brute Force)

Code

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int move_x[4] = {-1, 1, 0, 0};
int move_y[4] = {0, 0, -1, 1};


int main() {
    fastio;
    int n, s;
    cin >> n >> s;
    
    vector<int> v(n);
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }

    int result = 0;

    for(int i = 1; i < 1 << n; i++){
        int cur_sum = 0;
        for(int j = 0; j < n; j++) if(i & (1 << j)) cur_sum += v[j];
        if(cur_sum == s) ++result;
    }
    
    cout << result << "\n";
    return 0;   
}