백준 1450 [냅색문제]

문제

세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다.

N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

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

1450번: 냅색문제

 

---

이번 문제는 투포인터를 공부하다가 중간에서 만나기라는 알고리즘을 처음 봐서 당황했던 문제이다. 문제는 최대 30개의 물건과 무게가 주어지고, 무게 C까지 넣을 수 있는 가방에 이 물건들을 조합하여 넣을 수 있는 모든 경우의 수를 구하는 것이다. (물건을 아무것도 고르지 않는 것도 경우의 수에 포함)

 

처음엔 완전탐색을 생각해봤는데 2의 30승이 되버려서 당연히 시간초과가 날 것이라 생각했다. 

그리고 다음은 옛날에 풀었던 평범한 배낭에서 냅색알고리즘으로 DP를 사용한 것이 떠올랐는데 이번 문제랑은 상관없는 것 같아서 결국에는 DFS를 사용하되 최대한 예외상황을 제거하면서 만들었으나 시간초과가 났다.

 

결국 중간에서 만나기라는 알고리즘을 공부해 볼 수 밖에 없었고 생각보다 어렵지 않은 내용이었다.

 

30개의 물건을 완전탐색하면 2의 30승이 걸리지만 만약 이를 반으로 나눠서 완전탐색을 한면 2의 15승만 걸리는 개념을 적용한 것이 중간에서 만나기이다.

 

 중간에서 만나기는 다음과 같은 과정으로 진행한다.

 

    1. 물건의 무게를 기록한 배열 arr를 절반으로 나눠 arr1에 arr[0] ~ arr[n / 2]를 저장하고 arr2에 arr[n / 2 + 1] ~ arr[n - 1]을 저장한다.

    2. arr1과 arr2를 완전탐색해서 나온 결과들을 lst1과 lst2에 저장하고 정렬시킨다.

    3. lst1의 요소와 lst2의 요소를 합쳤을때  무게가 C이하인 경우의 수를 전부 찾아 출력한다.

 

1번과 2번을 통해 우리는 완전탐색을 2의15승의 시간복잡도로 끝낼 수 있다. 여기 까지만 보면 최적화가 잘 되어있다 생각할 수 있는데 3번이 중요하다.

3번을 그냥 완전탐색으로 진행하면 시간복잡도가 결국 2의 30승이 된다. 따라서 우리는 시간복잡도의 최적화를 3번에서 해야한다. 그 방법은 이분탐색을 이용하는 것이고 이를 위해 2번에서 lst들을 정렬시켜주는 것이다.

lst1의 요소 1개를 골라 이 값과 더했을 때 C를 초과하는 lst2 요소들의 첫번째 index를 이분탐색으로 찾아 경우의 수를 구한다. 예를 들면 다음과 같다.

 

ex) C = 8

index	0	1	2	3	4	5
lst1	3	4	5	6	7	8

index	0	1	2	3	4	5
lst2	1	3	5	7	9	11

(여기서 lst1의 index = 1인 요소 4와 더했을때 8이하가 되는 lst2의 요소들의 개수를 세보면 2개가 되므로 경우의 수에 +2를 해준다)

 

위와 같이 이분탐색으로 경우의 수를 찾는 과정을 lst1의 요소들에 대해 반복실행한다. 이때 밑에 코드에서는 이분탐색의 Upper bound를 이용해 C를 초과하는 lst2의 첫번째 요소의 index 값을 경우의 수의 개수로 하여 계산하였다.(위의 예시에서는 lst2의 index = 2의 요소부터 4와 더했을 때 C = 8을 초과하므로 경우의 수가 index인 2만큼 증가)

 

위 내용만 잘 이해하면 특별히 안쓰던 코드의 구조가 나오는 것이 아니라 문제를 쉽게 풀어낼 수 있을 것이다.

 

import java.io.*;
import java.util.*;
class Main {
    static long cnt = 0;
    static long binary_Search(ArrayList<Long> lst, long x){
        if (x < 0) return 0;
        else {
            int l = 0;
            int r = lst.size() - 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (lst.get(mid) > x)
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            return l;
        }
    }

    static void count(ArrayList<Long> lst1, ArrayList<Long> lst2, int c){
        for (int i = 0; i < lst1.size(); i++)
            cnt += binary_Search( lst2, c - lst1.get(i));
    }
    static void dfs(int[] arr, ArrayList<Long> lst, long sum, int p, int x){
        if (p != x){
            lst.add(sum + arr[p]);
            dfs(arr, lst, sum + arr[p], p + 1, x);
            dfs(arr, lst, sum, p + 1, x);
        }
    }
    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());
        int a = n / 2;
        int b = n - a;
        int[] arr1 = new int[a];
        ArrayList<Long> lst1 = new ArrayList<>();
        int[] arr2 = new int[b];
        ArrayList<Long> lst2 = new ArrayList<>();
        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());
        lst1.add(0L);
        lst2.add(0L);
        dfs(arr1, lst1, 0, 0, a);
        dfs(arr2, lst2, 0, 0, b);
        Collections.sort(lst1);
        Collections.sort(lst2);
        count(lst1, lst2, c);
        System.out.println(cnt);
    }
}