[백준] 1208번 부분수열의 합 2 - Java

문제 링크

https://www.acmicpc.net/problem/1208

문제

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

입력

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

출력

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

알고리즘: 중간에서 만나기, 이분 탐색

풀이

N이 40일 때 모든 부분 수열을 구하면 시간 초과가 난다. 그래서 중간에서 만나기라는 알고리즘을 사용해야 하는데, 방법은 간단하다. N의 길이를 가진 수열을 반으로 나눠주고, 각 수열에서 가능한 모든 부분 수열의 합을 구해서, 그 값을 이용해 S가 되는 부분 수열을 찾는 방법이다.

반으로 나누면 수열은 최대 길이가 20이고, 그 수열에서 부분 수열은 약 100만 개의 경우의 수가 나온다. 그렇기 때문에 반으로 나눈다는 아이디어만 생각하면, 간단하게 풀 수 있다.

여기서 나눠진 첫 번째 수열의 모든 부분 수열 합 리스트를 f_sum,
두 번째 수열의 모든 부분 수열 합 리스트를 s_sum, 이라고 하겠다.

f_sum을 반복문으로 돌면서 S-f_sum.get(i)값이 s_sum에 존재하는지 안 하는지 판단해준다. 이분 탐색을 이용해도 되지만, 나는 table로 s_sum을 구현해서 해당 값이 존재하는지 안 하는지 O(1)로 판단해줬다.

주의할 점은 f_sum과 s_sum에는 공집합을 의미하는 0을 꼭 넣어줘야 한다. 그래야 s_sum에만 존재하는 S, f_sum에만 존재하는 S의 경우의 수를 카운트해줄 수 있다. 단 S가 0일 때는 f_sum에 공집합 0과 s_sum에 공집합 0도 ans에 포함되기 때문에 이 경우는 -1을 해줘야 한다. -> (크기가 양수인 부분 수열 중이기 때문에)

소스 코드

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

public class Main {
    static int N,S;
    static int f_sn[];
    static int s_sn[];
    static Hashtable<Integer, Long> f_sum = new Hashtable<>();
    static Hashtable<Integer, Long> s_sum = new Hashtable<>();
    static long ans = 0;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        f_sn = new int[N/2];
        s_sn = new int[N-N/2];
        StringTokenizer n_st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            if(i<f_sn.length) f_sn[i] = Integer.parseInt(n_st.nextToken());
            else s_sn[i-f_sn.length] = Integer.parseInt(n_st.nextToken());
        }
        f_sum.put(0, 1L); //공집합
        s_sum.put(0, 1L); //공집합
        DFS(f_sn, 0, 0, f_sum);
        DFS(s_sn, 0, 0, s_sum);
        Iterator<Integer> keys = f_sum.keySet().iterator();
        while(keys.hasNext()) {
            int key = keys.next();
            int s_key = S - key;
            if(s_sum.get(s_key) != null) ans += f_sum.get(key) * s_sum.get(s_key);
        }
        if(S==0) ans -= 1; //S가 0이면 공집합 + 공집합 경우의 수도 추가됨 크기가 양수이기 때문에 -1
        System.out.println(ans);
    }
    
    static void DFS(int sn[], int ind, int sum, Hashtable<Integer, Long> table) {
        if(sn.length == ind) return;
        for(int i=ind; i<sn.length; i++) {
            int n_sum = sum + sn[i];
            if(table.get(n_sum)==null) table.put(n_sum, 1L);
            else table.replace(n_sum, table.get(n_sum)+1);
            DFS(sn, i+1, n_sum, table);
        }
    }
}