[BOJ] 1208. 부분 수열의 합 2 (🥇, 부분집합의 합)

🔗

💡

1182. 부분 수열의 합 문제와 유사한데 범위가 다르다. 1182번은 N = 20이라서 부분 집합을 전부 구해도 시간 초과가 발생하지 않지만(2^20 = 대략 백만) 1208번은 N = 40 이라서 시간 내에 구할 수 없다.

그래서 아래와 같이 반으로 나눠서 푸는 방식을 고려해볼 수 있다. 최대 40 길이를 반으로 나누게 되면 최대 20인 길이 내에서 부분 집합의 합을 구하기 때문에 아무리 오래 걸려도 2백만 정도의 연산만 수행하면 된다.

나눠서 부분 집합의 합을 구하는 것은 비트 연산을 사용했다.

static Map<Long, Long> getSubsetSum(long[] sequence, long S) {
    int n = sequence.length;
    Map<Long, Long> subsetSum = new HashMap<>();
    for (int i = 0; i < Math.pow(2, n); i++) {
        long tmpSum = 0;
        for (int j = 0; j < n; j++) {
            if ((i & (1 << j)) != 0) {
                tmpSum += sequence[j];
            }
        }
        
        subsetSum.put(tmpSum, subsetSum.getOrDefault(tmpSum, 0L) + 1);
    }
    return subsetSum;
}

왼쪽의 집합을 A 라고 하고 오른쪽 집합을 B 라고 할 때, A 집합에 있는 값 a 과 B 집합에 있는 값 b 를 합해서 S 가 될 수 있다면 전체 집합에서 합이 S 가 되는 집합이 존재한다는 뜻이 된다.

만약 A 에 부분집합의 합이 -1이 되는 집합의 개수가 3개이고 B에 부분집합의 합이 1이 되는 집합의 개수가 2라면 전체로 봤을 때는 2*3 해서 총 6 개의 부분집합의 합이 0이 될 수 있는 것이다.

A와 B 모두 합이 0이 되는 경우를 가지고 있는데 이 경우가 A 만 포함하거나 B만 포함하는 경우를 셀 수 있게 한다. 대신 둘 다 0인 경우는 공집합이 되기 때문에 문제의 조건에 어긋나서 만일 S = 0 인 경우를 구한다면 반드시 -1을 빼줘야한다(공집합의 합이라서)

⭕️

// 부분 수열의 합 2

package Baekjoon.Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class baekjoon_1208 {
        static Map<Long, Long> getSubsetSum(long[] sequence, long S) {
        int n = sequence.length;
        Map<Long, Long> subsetSum = new HashMap<>();
        for (int i = 0; i < Math.pow(2, n); i++) {
            long tmpSum = 0;
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) {
                    tmpSum += sequence[j];
                }
            }
            
            subsetSum.put(tmpSum, subsetSum.getOrDefault(tmpSum, 0L) + 1);
        }
        return subsetSum;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        long S = Long.parseLong(st.nextToken());

        long[] sequence = new long[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            sequence[i] = Long.parseLong(st.nextToken());
        }

        Map<Long, Long> A = getSubsetSum(Arrays.copyOfRange(sequence, 0, N / 2), S);
        Map<Long, Long> B = getSubsetSum(Arrays.copyOfRange(sequence, N / 2, N), S);

        long answer = 0;
        System.out.println(A);
        System.out.println(B);
        for (Long sum : A.keySet()) {
            answer += (A.get(sum) * B.getOrDefault(S - sum, 0L));
        }

        if (S == 0) answer--;
        System.out.println(answer);
    }
}