백준 1208 - 부분수열의 합 2

www.acmicpc.net/problem/1208

 

주어진 조건에서 부분수열을 생성하는 경우는 $2^{40}$으로 단순한 완전 탐색으로 풀 수 없다.

 

주어진 수열을 절반으로 나눈 상황을 가정해보자.

 

각 부분에서 수열을 생성하는 경우는 완전탐색으로 $2^{20}$이고 두개의 부분을 탐색해야 하므로 $2 \times 2^{20}$가 되어 각 부분의 부분수열을 구한 후 서로 결합하는 방법으로 문제를 해결 할 수 있게 된다.

 

이처럼 상태 공간을 반으로 나누고 두 상태 공간의 접점을 탐색하는 기법을 meet in the middle이라 부른다.

 

주어진 수를 서로 다른 배열에 담아 비트마스킹으로 부분수열의 합을 벡터에 저장하고 각 벡터에서 s의 개수 + 각 벡터에 있는 원소를 더했을 때 s가 되는 경우의 수를 구하면 답이 된다.

 

벡터의 원소를 더하는 경우는 이진 탐색을 통해 빠르게 구하도록 한다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
int n, s;
 
int ar1[20], ar2[20];
int idx1, idx2;
vector<int> a, b;
ll cnt;
 
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> n >> s;
    int mid = n / 2;
 
    for (int i = 0; i < mid; ++i)
        cin >> ar1[idx1++];
    for (int i = mid; i < n; ++i)
        cin >> ar2[idx2++];
 
    for (int i = 1; i < (1 << idx1); ++i)
    {
        int x = 0;
        for (int j = 0; j < idx1; ++j)
            if (i & (1 << j))
                x += ar1[j];
        
        a.push_back(x);
    }
    
    for (int i = 1; i < (1 << idx2); ++i)
    {
        int x = 0;
        for (int j = 0; j < idx2; ++j)
            if (i & (1 << j))
                x += ar2[j];
    
        b.push_back(x);
    }
 
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    cnt += upper_bound(a.begin(), a.end(), s) - lower_bound(a.begin(), a.end(), s);
    cnt += upper_bound(b.begin(), b.end(), s) - lower_bound(b.begin(), b.end(), s);
    for (int i = 0; i < a.size(); ++i)
        cnt += upper_bound(b.begin(), b.end(), s - a[i]) - lower_bound(b.begin(), b.end(), s - a[i]);
 
    cout << cnt;
}