[백준] 1450번 - 냅색문제 (Gold 1)

문제 링크

백준 1450번 - 냅색문제 (Gold 1)

문제 설명

물건의 개수 $N(\leq 30)$, 가방의 무게 한도 $C(\leq 10^{9})$가 주어진다.
각 물건의 무게가 주어져있을 때, 가방에 물건을 넣을 수 있는 방법의 수를 구하시오.
단, 아무것도 넣지 않는 경우도 한 가지로 센다.

정답 코드 및 설명

전체를 백트래킹으로 세려면 $2^{N}$가지를 세야하고, N이 30이하이므로 시간 초과가 나온다.
따라서, 절반으로 쪼개는 Meet in the middle(MITM) 알고리즘을 사용한다.
$N/2 \leq 15$이므로, 절반에 대해서는 모든 경우를 직접 탐색해도 최대 32,768가지 뿐이다.
전체 경우의 수를 구할 때는 이분탐색을 활용하였다.

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class BOJ1450 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        long c = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] value = new int[n];
        for (int i = 0; i < n; i++)
            value[i] = Integer.parseInt(st.nextToken());
        bw.write(ans(value, c) + "");
        bw.close();
    }

    static long ans(int[] value, long c) {
        long ans = 0;
        int[] value1 = Arrays.copyOfRange(value, 0, value.length / 2);
        int[] value2 = Arrays.copyOfRange(value, value.length / 2, value.length);
        ArrayList<long[]> count1 = count(value1);
        ArrayList<long[]> count2 = count(value2);
        // 누적합 : 무게 - (그 무게 이하로 담는 경우의 수)를 담은 리스트를 생성
        for (int i = 1; i < count2.size(); i++) {
            long sum = count2.get(i - 1)[1];
            count2.set(i, new long[] { count2.get(i)[0], count2.get(i)[1] + sum });
        }
        // 가방 = 가방1 + 가방2로 쪼개서 생각
        for (int i = 0; i < count1.size(); i++) {
            // 가방 1에는 count1.get(i)[0] 무게가 들어감
            long max2 = c - count1.get(i)[0]; // 가방 2에 담을 수 있는 최대 무게
            if (max2 < 0)
                break;
            int j = 0, end = count2.size();
            // 이분탐색
            while (j + 1 < end) {
                int mid = (j + end) / 2;
                if (count2.get(mid)[0] <= max2)
                    j = mid;
                if (count2.get(mid)[0] > max2)
                    end = mid;
            }
            // 가방 1에 count1.get(i)[0] 무게가 들어간 경우의 가짓수
            ans += count1.get(i)[1] * count2.get(j)[1];
        }
        return ans;
    }

    static int[] seq;

    // 물건이 주어져있을 때, 무게 - 경우의 수를 담고 있는 리스트를 생성
    static ArrayList<long[]> count(int[] value) {
        TreeMap<Long, Long> map = new TreeMap<>();
        map.put(0L, 1L); // 아무것도 담지 않는 경우 고려
        seq = new int[value.length];
        backtracking(value, map, 0);
        return mapToList(map);
    }

    static long sum = 0;

    // 모든 경우를 탐색하는 백트래킹 : 아무것도 넣지 않는 경우는 고려되지 않는다
    static void backtracking(int[] value, TreeMap<Long, Long> map, int depth) {
        int n = value.length;
        if (depth == n)
            return;
        for (int i = 0; i < n; i++) {
            if (depth == 0 || seq[depth - 1] < i) {
                sum += value[i];
                seq[depth] = i;
                map.put(sum, map.getOrDefault(sum, 0L) + 1);
                backtracking(value, map, depth + 1);
                sum -= value[i];
                seq[depth] = -1;
            }
        }
    }

    static ArrayList<long[]> mapToList(TreeMap<Long, Long> map) {
        ArrayList<long[]> mapToList = new ArrayList<>();
        ArrayList<Long> keys = new ArrayList<Long>(map.keySet());
        ArrayList<Long> values = new ArrayList<Long>(map.values());
        for (int i = 0; i < keys.size(); i++)
            mapToList.add(new long[] { keys.get(i), values.get(i) });
        return mapToList;
    }
}