[BOJ] 백준 1208 - 부분수열의 합 2

문제 링크

www.acmicpc.net/problem/1208

1208번: 부분수열의 합 2

 

풀이

나이브한 풀이는 $O(2^N)$ 완전탐색입니다. 물론 터집니다.

 

1) 주어진 입력을 절반으로 나누고, 각각 $2^{\frac{N}{2}}$ 의 완전 탐색을 돌려 모든 조합을 구합니다. 이렇게 구한 조합들을 $a, b$라 합시다.

2) $b$를 정렬하고, $a$의 모든 원소 $i$에 대해, $b$에서 $s - i$값을 가진 원소들을 찾아줍니다. upper bound, lower bound를 이용하면 같은 원소들의 개수를 쉽게 얻을 수 있습니다.

3) 만약 $s$가 0인 경우 정답에서 1을 빼주도록 합시다. ($a$에서 아무것도 안 고르는 경우) + ($b$에서 아무것도 안 고르는 경우)에도 값의 합이 0이기 때문에 이 케이스를 제외하기 위해 빼주어야 합니다.

 

정답 코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using vll = vector<ll>;


ll n, s;
ll p[44];
vll a, b;

void go(int i, int last, ll sum, vll &x) {
    if (i == last) {
        x.push_back(sum);
        return;
    }
    go(i + 1, last, sum + p[i], x);
    go(i + 1, last, sum, x);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> s;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    go(0, n / 2 + 1, 0, a);
    go(n / 2 + 1, n, 0, b);

    sort(all(b));

    ll ans = 0;
    for (ll i: a) {
        auto l = lower_bound(all(b), s - i);
        auto u = upper_bound(all(b), s - i);
        ans += u - l;
    }
    if (s == 0) ans--;
    cout << ans;
}