[Boj_1208] 부분수열의 합 2

📎 문제 링크

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

 

▸ 문제

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

 

▸ 입력

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

 

▸ 출력

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

 

📍 문제 정보

• 🥇  문제 레벨 : 골드 1
• 🔔  문제 유형 : 이분 탐색, 중간에서 만나기
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

N개의 정수가 주어졌을 때, 크기가 양수인 부분수열 중에서 원소 합이 S가 되는 경우의 수를 구하는 문제이다.

단, N은 최대 40이므로 단순한 부분집합 탐색으로는 시간 초과 가능성이 크다.

 

그러므로 Boj_1450 냅샙문제에도 활용했던 중간에서 만나기(Meet in the middle) 알고리즘을 사용하여 해결할 수 있다.

 

1️⃣ 배열 나누기

배열을 반으로 나누고, 각 절반에서 가능한 부분집합의 합을 전부 리스트에 저장한다.

이때, 재귀 함수를 이용해 모든 조합을 탐색한다.

private static void comb(int start, int end, ArrayList<Integer> list, int sum) {
    if (start == end) {
        list.add(sum);
        return;
    }

    comb(start+1, end, list, sum+arr[start]); // 현재 원소 포함
    comb(start+1, end, list, sum); // 현재 원소 미포함
}

• start부터 end 전까지 모든 부분집합의 합을 구해 list에 저장한다.
• 이렇게 하면 왼쪽 절반(left)와 오른쪽 절반(right)의 모든 부분집합의 합을 구할 수 있다.

 

2️⃣ 두 리스트의 조합으로 S 만들기

왼쪽 리스트의 각 원소 x에 대해, 오른쪽 리스트에서 S-x가 몇 번 등장하는지를 찾아 카운트한다.

이를 효율적으로 하기 위해 오른쪽 리스트를 정렬한 뒤, 이진 탐색을 사용한다.

 

3️⃣ 이진 탐색, lower_bound와 upper_bound

private static int upperBound(ArrayList<Integer> list, int target) {
    int left = 0;
    int right = list.size();

    while (left < right) {
        int mid = (left+right)/2;

        if (list.get(mid) <= target) left = mid+1;
        else right = mid;
    }

    return right;
}

private static int lowerBound(ArrayList<Integer> list, int target) {
    int left = 0;
    int right = list.size();

    while (left < right) {
        int mid = (left+right)/2;

        if (list.get(mid) >= target) right = mid;
        else left = mid+1;
    }

    return right;
}

• lowerBound : target 이상이 처음 나오는 위치
• upperBound : target 초과가 처음 나오는 위치
• 정렬된 리스트일 때, upperBound - lowerBound가 target의 등장 횟수가 된다.

 

⚠️ 공집합 처리

각 리스트 (left, right)에는 공집합 합(0)이 포함된다.

문제에서 크기가 양수인 부분수열만 세야 하므로, S==0인 경우에는 두 공집합을 동시에 선택하는 경우를 빼주어야 한다.

 

위 풀이의 코드를 바탕으로 전체적인 코드를 작성해 보면 아래와 같다.

 

✔ 코드

메모리 : 80096KB
시간 : 1268ms

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 int[] arr;
    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());
        int s = Integer.parseInt(st.nextToken());

        arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        ArrayList<Integer> left = new ArrayList<>();
        ArrayList<Integer> right = new ArrayList<>();
        comb(0, n/2, left, 0);
        comb(n/2, n, right, 0);
        Collections.sort(right);

        long ans = 0;
        for (int i = 0; i < left.size(); i++) {
            int target = s-left.get(i);
            int upper = upperBound(right, target);
            int lower = lowerBound(right, target);
            ans += upper - lower;
        }

        System.out.println(s == 0 ? ans-1 : ans);

        br.close();
    }

    private static int upperBound(ArrayList<Integer> list, int target) {
        int left = 0;
        int right = list.size();

        while (left < right) {
            int mid = (left+right)/2;

            if (list.get(mid) <= target) left = mid+1;
            else right = mid;
        }

        return right;
    }

    private static int lowerBound(ArrayList<Integer> list, int target) {
        int left = 0;
        int right = list.size();

        while (left < right) {
            int mid = (left+right)/2;

            if (list.get(mid) >= target) right = mid;
            else left = mid+1;
        }

        return right;
    }

    private static void comb(int start, int end, ArrayList<Integer> list, int sum) {
        if (start == end) {
            list.add(sum);
            return;
        }

        comb(start+1, end, list, sum+arr[start]);
        comb(start+1, end, list, sum);
    }
}