[BOJ] 1208 - 부분수열의 합 2 JAVA

www.acmicpc.net/problem/1208

1208번: 부분수열의 합 2

문제

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

입력

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

출력

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

예제 입력 1

5 0

-7 -3 -2 5 8

예제 출력 1

1

 

 

 

 

 

 

 

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static int[] arr = null;
    static ArrayList<Integer> first = null;
    static ArrayList<Integer> second = null;
    static int N, S, ans;

    public static int lowerBound(ArrayList<Integer> list, int target) {
        int min = 0;
        int max = list.size();
        while(min < max) {
            int mid = (min + max) / 2;
            if(list.get(mid) >= target) {
                max = mid;
            }else {
                min = mid + 1;
            }
        }
        return max;
    }

    public static int upperBound(ArrayList<Integer> list, int target) {
        int min = 0;
        int max = list.size();
        while(min < max) {
            int mid = (min + max) / 2;
            if(list.get(mid) <= target) {
                min = mid + 1;
            }else {
                max = mid;
            }
        }
        return max;
    }

    public static void dfs(int dept, int end, int sum, ArrayList<Integer> list) {
        if (dept == end) {
            list.add(sum);
            return;
        }
        dfs(dept + 1, end, sum + arr[dept], list);
        dfs(dept + 1, end, sum, list);
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        arr = new int[N + 1];
        first = new ArrayList<>();
        second = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 배열을 절반으로 나눠 각각 부분집합의 합의 리스트를 구한다.
        dfs(0, N / 2, 0, first);
        dfs(N / 2, N, 0, second);
        Collections.sort(first);
        Collections.sort(second);

        // 한 리스트에 대해 각 원소에 더했을 때 S를 완성할 수 있는 타겟의 수를 찾는다.
        long ans = 0;
        for(int i = 0; i < first.size(); i++) {
            int target = S - first.get(i);
            int upper = upperBound(second, target);
            int lower = lowerBound(second, target);
            ans += upper - lower;
        }
        System.out.println(S == 0 ? ans - 1 : ans);
    }
}

 

codeung.tistory.com/223 이 문제에서 N 제한이 두 배로 늘어난 문제.

 

같은 방법으로 풀었다가 시간 초과를 맞았다.

N의 상한은 40이므로 같은 방법으로 풀면 O(2^N) = 약 1조의 값으로 터져버린다.

 

구글링을 통해 정답을 확인했고 현재 수준으로는 절대 혼자서 해결할 수 없는 문제였다.

 

"중간에서 만나기"  (Meet in the middle) 방법을 사용해야 한다.

 

주어진 배열을 절반으로 나누어 각각 부분집합을 구한다.

(정확하게는 부분집합의 원소들을 모두 더한 값을 원소로 하는 리스트를 구한다.)

 

두 리스트에 대해서 서로의 원소의 합을 통해 S를 만들 수 있는 경우의 수를 구하면 된다.

이분탐색으로 target을 찾기 위해 먼저 정렬을 해놓아야 한다.

 

어차피 두 리스트 모두 처음 주어진 배열에 대한 부분집합이기 때문에 두 리스트의 원소를 더해서 S를 만들어도 상관 없다.

 

부분집합의 개수는 총 2^N개가 존재할 수 있고 이 경우 N의 상한이 40이므로 int 범위를 초과할 수 있기 때문에 long을 사용해야 한다.

 

 

 

이분 탐색을 사용한 upperBound(), lowerBound()는 그냥 외워버리자.