BOJ 1208 부분집합의 합 2

부분집합의 합 2

(http://boj.kr/1208)

부분집합의 합 문제는 \(N\)의 제한이 \(20\)이기 때문에 모든 부분집합을 구하는 \(2^N\)의 방법으로도 풀 수 있었다.

하지만 이 문제는 \(N\)의 제한이 \(40\)이기 때문에 같은 방법으로는 풀 수 없다.

풀이부터 말하자면,

배열을 반으로 나눠서 \(A\)와 \(B\)라고 했을 때,

\(A\)의 부분집합의 합이 \(S\)가 되는 경우 + \(A\)와 \(B\)의 부분집합의 합이 \(S\)가 되는 경우 + \(B\)의 부분집합의 합이 \(S\)가 되는 경우를 구해야 한다.

앞의 경우와 뒤의 경우는 그냥 구하면 \(2\times 2^{\frac{N}{2}}\)만에 구할 수 있고,

가운데의 경우를 구하기 위해서는 \(A\)와 \(B\)를 합쳐야 한다.

처음에는 \(A\)에서 나오는 합을 센다. 그 다음에 \(B\)의 합을 구하면서 (\(S\) - 합)이 \(A\)에서 몇 번 있었는지를 확인하면 쉽게 구할 수 있다.

처음에는 dp처럼 d[i][j] = d[i - 1][j] + d[i - 1][s - arr[i]]의 방법으로 풀려고 했는데, 메모리가 부족했다.

더 좋은 방법이 생각 안 나서 풀이를 찾아 봤는데, 반으로 나눈다는 방법으로 시간을 훨씬 줄일 수 있다는 것이 신기했다.

냅색문제와 매우 비슷하다.

#include <cstdio>
 
int arr[40], n, s, a[4000001];
long long cnt;
 
void f(int p, int t, bool c) {
    if (p == n / 2) {
        if (c == false)
            return;
        if (t == s)
            cnt++;
        a[t + 2000000]++;
 
        return;
    }
 
    f(p + 1, t + arr[p], true);
    f(p + 1, t, c);
}
 
void g(int p, int t, bool c) {
    if (p == n) {
        if (c == false)
            return;
        if (t == s)
            cnt++;
        if (s - t > 2000000 || s - t < -2000000)
            return;
        cnt += a[s - t + 2000000];
 
        return;
    }
 
    g(p + 1, t + arr[p], true);
    g(p + 1, t, c);
}
 
int main() {
    int i;
 
    scanf("%d %d", &n, &s);
 
    for (i = 0;i < n;++i)
        scanf("%d", &arr[i]);
 
    f(0, 0, false);
    g(n / 2, 0, false);
 
    printf("%lld", cnt);
 
    return 0;
}