[BOJ] 1208

부분수열의 합 2

1208번 https://www.acmicpc.net/problem/1208

분류

• Gold 1

• 이분 탐색
• 중간에서 만나기

해법

BOJ_3273: 두 수의 합 문제의 심화버전입니다.

N이 40인데, 모든 부분수열의 합을 완전탐색으로 구하면 2^N으로 TLE가 나옵니다.
따라서, 반으로 나눠서 양쪽의 모든 부분수열의 합을 구한 후 양쪽을 합쳐서 S를 만들 수 있는 경우를 계산하면 시간 안에 통과할 수 있습니다.

정답 코드

/*
BOJ 1208: 부분수열의 합 2
*/

#include <bits/stdc++.h>
using namespace std;

int n, s;
int arr[45];
unordered_map<int, int> m;
long long res;

void l() {
    queue<int> q;
    q.push(0);
    for (int i = 0; i < n / 2; i++) {
        int sz = q.size();
        while (sz--) {
            int cur = q.front(); q.pop();
            q.push(cur);
            q.push(cur + arr[i]);
        }
    }
    while (!q.empty()) {
        m[q.front()]++;
        q.pop();
    }
}

void r() {
    queue<int> q;
    q.push(0);
    for (int i = n / 2; i < n; i++) {
        int sz = q.size();
        while (sz--) {
            int cur = q.front(); q.pop();
            q.push(cur);
            q.push(cur + arr[i]);
        }
    }
    while (!q.empty()) {
        res += m[s - q.front()];
        q.pop();
    }
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> s;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    l(); r();
    if (s == 0) res--;
    cout << res;
    return 0;
}