BOJ_1208_부분수열의 합 2 (Java)

[Gold I] 부분수열의 합 2 - 1208

문제 링크

성능 요약

메모리: 98592 KB, 시간: 672 ms

분류

이분 탐색, 중간에서 만나기

제출 일자

2025년 5월 10일 18:15:10

문제 설명

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

문제 풀이

중간에서 만나기를 사용했다.

너무 길어 $2^{40}$이 되면 연산이 초과나므로 $2^{20}$으로 두 부분으로 나눴다. 이러면 10억보다 작아서 가능.

한쪽을 HashMap에 값과 개수를 저장하고,

나머지 배열에서 (N-S) 와 같은 느낌으로 합해서 N을 만들지만 이전에 S가 있었다면 이번에 N-S를 찾는 느낌으로 이런 값을 찾아서 있으면 그 개수만큼씩 반영.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, S;
    static int[] arr1, arr2;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_1208_부분수열의합2/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        arr1 = new int[N / 2];
        arr2 = new int[N - arr1.length];

        for (int i = 0; i < arr1.length; i++) {
            arr1[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = 0; i < arr2.length; i++) {
            arr2[i] = Integer.parseInt(st.nextToken());
        }

        HashMap<Integer, Long> arr1CombCnt = new HashMap<>();
        for (int i = 0; i < (1 << arr1.length); i++) {
            int sum = 0;
            for (int j = 0; j < arr1.length; j++) {
                if ((i & (1 << j)) != 0) sum += arr1[j];
            }
            arr1CombCnt.put(sum, arr1CombCnt.getOrDefault(sum, 0L) + 1);
        }

        long res = 0;

        for (int i = 0; i < (1 << arr2.length); i++) {
            int sum = 0;
            for (int j = 0; j < arr2.length; j++) {
                if ((i & (1 << j)) != 0) sum += arr2[j];
            }
            int target = S - sum;
            if (arr1CombCnt.containsKey(target)) res += arr1CombCnt.get(target);
        }
        if (S == 0) res--;
        System.out.println(res);
        bw.flush();
        bw.close();
        br.close();
    }
}