백준 1208 부분수열의 합2

문제

수열과 값이 주어질 때 부분 수열의 합이 그 값이 되는 경우의 수를 찾아라

풀이

반으로

배열을 반을 갈라서 앞 배열에서 S가 나오는 경우의 수 + 뒷 배열에서 S가 나오는 경우의 수 + 앞 뒤 배열에서 S가 나오는 경우의 수

처음엔 이해가 안됐지만….

부분수열의 합1과 비슷하게 풀 수 있다. N이 20일 때는 $2^{20}=1,000,000$ 으로 완탐으로 풀렸지만 이 문제는 N이 40으로 $2^{40}=1,000,000,000,000$ 으로 절대 안돼

따라서 S를 찾기 위해 배열은 반으로 갈라서 왼쪽 배열에서 나올 수 있는 합들과 오른쪽 배열에서 나올 수 있는 합들을 구해놓는다. 그리고 이분 탐색을 통해 해결

$O(2^{N/2})$

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int N, S;
vector<int> perm;

void solve(int pos, int end, int sum, vector<int> &p) {
    if (pos == end) {
        p.emplace_back(sum);
        return;
    }
    solve(pos + 1, end, sum + perm[pos], p);
    solve(pos + 1, end, sum, p);
}

int main() {
    cin >> N >> S;
    perm.resize(N);
    for (auto &p:perm) {
        cin >> p;
    }
    vector<int> left, right;
    solve(0, N / 2, 0, left);
    solve(N / 2, N, 0, right);
    sort(right.begin(), right.end());

    long long ret = 0;
    for (auto &val:left) {
        int target = S - val;
        auto hi = upper_bound(right.begin(), right.end(), target);
        auto low = lower_bound(right.begin(), right.end(), target);
        ret += hi - low;
    }
    cout << (S == 0 ? ret - 1 : ret);
    return 0;
}

Written by@[jungin]

안녕하세요

GitHub