[백준] 1208 - 부분집합의 합2

이 문제는 저도 참고하고 풀었습니다

처음 접근은 크기가 40밖에 되지 않아서 정렬하고 구간으로 나누어 S가 되는 것을 카운팅 했으나

-10 3 10의 경우 S가 0일때 답은 1, 하지만 제가 푼 방법으로는 0이 나왔기에 잘못됬다는 것을 알았습니다.

이 문제를 해결하기 위해서 먼저 배열을 양쪽으로 나누어 나올 수 있는 모든 합의 경우의 수를 L, R로 나누어 저장

그리고 나서 L에서의 하나의 값과 R에서 나오는 값이 합이 S가 되는 갯수를 세어주면 됬습니다.

하지만 N = 40일 경우 각각 경우의 수가 1048575개 씩 나오기 때문에 모두 비교하기 보다는,

두개의 합이 S가 되는 시작점, S보다 커지는 시작점을 R에서 찾아서 그 위치의 차를 더해주었습니다.

#include <iostream>
#include <algorithm>
#define MX 42
using namespace std;
 
long long arr[MX];
long long L[MX*MX*MX*MX], R[MX*MX*MX*MX];
int N, S, l, r;
long long dab = 0;
 
void dfs(int d, int pos, int end, long long sum, int dir)
{
    if (pos == end)
    {
        if (dir) L[++l] = sum;
        else R[++r] = sum;
        return;
    }
    dfs(d + 1, pos + 1, end, sum, dir);
    dfs(d + 1, pos + 1, end, sum + arr[pos], dir);
}
 
int main(void)
{
    cin >> N >> S;
    for (int i = 0; i < N; i++)
        cin >> arr[i];
 
    l = r = -1;
    dfs(0, 0, N / 2, 0, 1);
    dfs(0, N / 2, N, 0, 0);
    sort(R, R + (r + 1));
 
    for (int i = 0; i <= l; i++)
    {
        int t = S - L[i];
        auto lb = lower_bound(R, R + (r + 1), t);
        auto ub = upper_bound(R, R + (r + 1), t);
        dab += ub - lb;
    }
    if (S == 0) dab--;
    cout << dab << endl;
}