190217 BOJ 1208번 부분집합의 합 2

분할 정복, 브루트 포스

- N = 40 이면 공집합을 뺀 부분집합의 갯수는 2^40 - 1...

- 그대로 완전 탐색을 할 수 없으니 두 집합으로 나눠서 세면 된다

- 답이 될 수 있는 경우의 수가 int를 초과하므로 long long 으로 해줘야 한다. 이것 때문에 몇 번을 틀렸다ㅜㅜ

풀이

1. 입력받은 40개의 정수를 반으로 나눈다.

2. 두 개로 나눈 정수들을 가지고 집합을 만든다.

3. 집합을 만들 때 공집합을 제외시키고 합이 S 인 경우를 세준다.

4. 만든 집합들을 정렬하고 upper_bound, lower_bound를 이용해 갯수를 센다.

소스 코드

#include <iostream>
#include <algorithm>
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define endl '\n'
#define ll long long
#define mp(a,b) make_pair(a,b)
#define sws ios::sync_with_stdio(false), cin.tie(NULL)
#define MAX 200000000
#define pii pair<int, int>
using namespace std;
int N, S, az, bz;
ll ans;
int arr[42];
vector<int> A, B, C, D;
void make_set(int idx, int sm, bool flag) {
    if (idx == az) {
        if (flag) C.push_back(sm);
        if (flag && sm == S) ans++;
        return;
    }
    make_set(idx + 1, sm + A[idx], true);
    make_set(idx + 1, sm, flag);
}
void make_set2(int idx, int sm, bool flag) {
    if (idx == bz) {
        if(flag) D.push_back(sm);
        if (flag && sm == S) ans++;
        return;
    }
    make_set2(idx + 1, sm + B[idx], true);
    make_set2(idx + 1, sm, flag);
}
int main() {
    sws;
    cin >> N >> S;
    FOR(i, 0, N) cin >> arr[i];
    if (N == 1) {
        if (arr[0] == S) cout << 1;
        else cout << 0;
        return 0;
    }
    FOR(i, 0, N / 2) A.push_back(arr[i]);
    FOR(i, N / 2, N) B.push_back(arr[i]);
    az = A.size(), bz = B.size();
    //분할 정복
    //A,B의 부분집합들을 구하고 합들을 저장
    make_set(0, 0, false);
    make_set2(0, 0, false);
    sort(C.begin(), C.end());
    sort(D.begin(), D.end());
    int cz = C.size();
    FOR(i, 0, cz) {
        int ss = S - C[i];
        int up = upper_bound(D.begin(), D.end(), ss) - D.begin();
        int lo = lower_bound(D.begin(), D.end(), ss) - D.begin();
        ans += up - lo;
    }
    cout << ans;
}