[백준 골드1] 1450번: 냅색문제 (이분탐색, 중간에서 만나기) - Java

"스파르타코딩클럽 작심큰일 챌린지" 2일차 챌린저 문제

---

1450번: 냅색문제

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

 

문제
세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다.
N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다.

출력
첫째 줄에 가방에 넣는 방법의 수를 출력한다.

예제 입력 1 
2 1
1 1
예제 출력 1 
3
예제 입력 2 
1 1
1
예제 출력 2 
2
예제 입력 3 
1 2
1
예제 출력 3 
2
예제 입력 4 
2 1
2 2
예제 출력 4 
1
예제 입력 5 
2 2
1 1
예제 출력 5 
4
예제 입력 6 
30 30
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
예제 출력 6 
1073741824

---

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

풀이

물건을 넣음을 1로, 넣지 않음을 0으로 생각하고, 가방에 넣는 모든 물건들의 조합(부분집합)을 비트마스킹으로 풀 수 있겠다고 생각했다.

그런데 N<=30이기 때문에 N=30인 배열을 이진수로 표현한다면 2^30자리가 되고, 완전탐색하는 경우의 수가 2^30이므로 시간 초과가 날 것으로 생각되었다.

내 수준에서는 방법을 떠올릴 수 없어 찾아본 결과 '중간에서 만나기(meet in the middle)' 알고리즘을 알게 되었다.

 

'중간에서 만나기' 알고리즘은 긴 배열을 완전탐색하는 대신, 배열을 절반으로 쪼개어 각각에 대해 연산하고 두 과정에서의 계산값을 활용해 더욱 효율적으로 연산한다. (기존 길이 n -> 길이 n/2 2개)

 

이를 활용해 로직을 아래와 같이 설계할 수 있고, 각 단계의 시간복잡도를 나타내면 아래와 같다.

1. 왼쪽 집합의 모든 부분집합 경우의 수 계산해 해당 경우의 무게 합을 list1에 저장 -> 2^15

2. 오른쪽 집합의 모든 부분집합 경우의 수 계산해 해당 경우의 무게 합을 list2에 저장 -> 2^15 (아래 코드에서는 left를 파라미터로 전달해 탐색 시작 인덱스를 다르게 했다.)

3. 한 리스트(list2)를 정렬하고, 다른 한쪽 리스트(list1) 값을 하나씩 꺼내 key로 하여 이진탐색 -> 2^15*log2^15

=> 시간복잡도 O(2^16)

 

3번 구현 추가 설명:

최대 담을 수 있는 물건의 무게가 c이고, list1에서 꺼낸 값(무게 합)이 a일때, list2를 통해서 담을 수 있는 최대 무게는 c-a이고, 이진탐색을 통해 c-a 이하로 담을 수 있는 경우를 찾아야 한다.

list2를 이진탐색해서 b=c-a인 b를 찾았는데 그때의 인덱스가 x라면, list2가 정렬되어있기 때문에 x+1개를 가능한 갯수로 바로 연산할 수 있다. (아래 코드에서는 left=mid+1에 의해 +1 연산이 있다)

 

공부에 참고한 글들: https://banwolcode.tistory.com/51(dfs), https://myunji.tistory.com/364(비트마스킹)

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

public class Main
{
    private static List<Long> subsetSum(int[] arr, int left, int len) {
        List<Long> result = new ArrayList<>();
        int limit = 1 << len; // 비트마스킹으로 여부를 확인
        for (int i = 0; i < limit; i++) {
            long sum = 0;
            for (int j = 0; j < len; j++) { // len자리의 이진법 수에서
                if (((i >> j) & 1) == 1) { // 값이 1인 자리를 체크해 저장
                    sum += arr[left+j];
                }
            }
            result.add(sum);
        }
        return result;
    }

    static long binarySearch(List<Long> list, long key) {
        if (key < 0)
            return 0;
        long left = 0;
        long right = list.size();
        while (left < right) {
            long mid = (left + right) / 2;
            if (list.get((int)mid) <= key)
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }

    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 c = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        long cnt = 0;
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(st.nextToken());
        List<Long> list1 = subsetSum(arr, 0, n/2);
        List<Long> list2;
        if (n%2==0) list2 = subsetSum(arr, n/2, n/2);
        else list2 = subsetSum(arr, n/2, n/2+1);
        Collections.sort(list2); // 정렬
        for (int i = 0; i < list1.size(); i++)
            cnt += binarySearch(list2, c-list1.get(i));
        System.out.println(cnt);
    }
}