[백준] 1450번 냅색문제

문제 설명

• https://www.acmicpc.net/problem/1450
• Gold 1

문제 풀이

• 문제는 일반적인 0/1 냅색으로 풀이할 수 없다. (공간복잡도가 너무큼)
• 또한 완전 탐색은 2^30 가지수가 나오므로 시간복잡도를 초과한다.
• Meet in the middle(중간에서 만나기)를 통해 시간복잡도를 줄여서 풀이하였다.
• 풀이를 위한 개요는 아래와 같다.

  1. 물건 집합을 두개로 나뉘어 각 집합이 가질 수 있는 경우의 수를 구한다. (2^15)
  2. 각 집합의 원소를 서로 매칭시켜 최대 무게보다 낮은지를 확인한 후 경우의 수에 포함시킨다.

• 위의 2번 과정은 단순하게 진행하면 (2^15) x (2^15)로 시간복잡도를 초과하지만 이분탐색을 통하여 시간복잡도를 충족시킬 수 있다.
• 아래 코드 참조

소스 코드 (JAVA)

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

class Main {

    static BufferedReader br;
    static BufferedWriter bw;

    static int N, C;
    static int[] arr1, arr2;
    static List<Long> res1, res2;

    public static long binarySearch(List<Long> res, long x) {
        if ( x < 0 ) return 0;
        else {
            int l = 0;
            int r = res.size() - 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (res.get(mid) > x)
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            return l;
        }
    }

    public static void dfs(int ind, int[] arr, List<Long> res, long sum) {
        if (ind != arr.length) {
            res.add(sum + arr[ind]);
            dfs(ind+1, arr, res, sum + arr[ind]);
            dfs(ind+1, arr, res, sum);
        }
    }

    public static void solve() throws IOException {
        dfs(0, arr1, res1, 0);
        dfs(0, arr2, res2, 0);
        Collections.sort(res1);
        Collections.sort(res2);
        long result = 0;
        for (int i = 0; i < res1.size(); i++)
            result += binarySearch(res2, C - res1.get(i));
        bw.write(result + "\n");
        bw.flush();
    }


    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        int a = N / 2;
        int b = N - a;
        arr1 = new int[a];
        arr2 = new int[b];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < a; i++)
            arr1[i] = Integer.parseInt(st.nextToken());
        for (int i = 0; i < b; i++)
            arr2[i] = Integer.parseInt(st.nextToken());
        res1 = new ArrayList<>();
        res2 = new ArrayList<>();
        res1.add(0L);
        res2.add(0L);
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}


/**
 * N개의 물건, 최대 C만큼 담을 수 있는 가방
 */