[Meet in the middle] 백준 1450 냅색 문제

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

1450번: 냅색문제

브루트포스로 문제를 해결하기에는 N 이 너무 큰 경우에 시간 초과가 발생할 수 있다.

 

이때 다양한 방법으로 최적화를 시도할 수 있겠지만,

 

분할정복처럼 N 을 절반씩 나눠서 연산한 다음에 결과를 합쳐서 문제를 푸는 것을 

 

meet in the middle 알고리즘이라고 한다. 

 

다만, 재귀적으로 반복해서 N/2, N/4 ... 1 처럼 계속 쪼개는 게 아니고

 

맨 처음에 1회만 반으로 쪼개는 것이다.

 

예를 들어 길이가 40 인 수열이 주어졌을 때, 이 수열들을 이루는 원소들 중 몇 개를 

 

중복해서 더한 값이 특정 값이 되도록 하는 조합이 얼마나 존재하는 지 알아내야 한다고 생각해보자.

 

그러면, 모든 원소를 순회하면서 i 번째 원소를 포함할 지 말 지를 결정해주면 되지만

 

해당 방법은 2^40 번의 연산이 필요하고 이는 대부분의 경우에서 시간 초과가 발생한다.

 

이를 최적화하기 위해서 길이가 40 인 수열을 절반으로 나누어보자.

 

각각의 수열을 탐색하는 경우의 수는 2^20 이므로 2^20*2 ~= 2^21 만큼의 연산이 필요할 것이다.

 

근데 나누어서 어떻게 하려는 걸까?

 

발상은 간단하다.

 

0~n/2 까지의 배열을 lv, n/2~n 까지의 배열을 rv 라고 하자.

 

그러면 lv 의 원소를 순회하면서 target -  lv[i] 가 rv 에 몇 개 존재하는 지 구해주면 된다.

 

이를 위해서는 이분 탐색을 이용하는 것이 일반적이다.

 

정리하면 meet in the middle 알고리즘은 n^m 의 연산을 2*n^(m-1) 의 연산으로 줄일 수 있다.

 

 문제에 적용해보자.

 

냅색 문제(백준 1450)는 전형적인 meet in the middle 알고리즘을 이용하는 문제이다.

 

N 개의 물건을 가지고 있고, 최대 C 만큼의 무게를 넣을 수 있을 때

N 개의 물건을 가방에 넣을 수 있는 경우의 수를 찾아내야 한다.

 

어떻게 할까?

 

N <= 30 이므로 완전탐색하는 경우에는 최대 2^30 ~= 1073741824 번의 연산이 필요할 것이다.

 

대충 10 초 정도가 걸릴 것 같은데, 위 문제의 시간 제한은 1초이므로 최적화가 필요하다.

 

만약에 meet in the middle 알고리즘을 사용한다면 어떨까?

 

2^15*2 ~=  65536 번의 연산과 이분탐색(nlogn)에 의해

총 65536 + 65536 * long(65536) ~= 65536 + 5 * 65536 ~=  393216 번의 연산이 필요할 것이라고 추측할 수 있다.

 

즉, meet in the middle 알고리즘으로 위 문제를 시간제한 1초 안에 넉넉하게 해결이 가능함을 검증할 수 있었다.

 

구현하기 전에 어떻게 풀어야 할 지 설계를 해보자.

 

n 개의 배열 중에서 i 개를 선택하여 더한 것이 c 이하인 조합의 수를 구하면 되고

 

이를 위해서 우리는 meet in the middle 알고리즘을 사용하기로 했다.

 

길이가 n 인 arr 배열의 0~n/2 까지의 원소들로 만들어 낼 수 있는 부분 합의 배열을 lv

 

길이가 n 인 arr 배열의 n/2~n 까지의 원소들로 만들어 낼 수 있는 부분 합의 배열을 rv 라고 하자.

 

부분합을 구하려면 dfs 를 이용하는 방법이 있다.

 

private static void dfs(int s, int e, long sum, ArrayList<Long> v) {
    if (s >= e) {
        v.add(sum);
        return;
    }
    dfs(s + 1, e, sum, v);
    dfs(s + 1, e, sum + arr[s], v);
}

위 코드와 같이 시작점과 끝 점 그리고 부분합을 매개변수로 받는 함수를 구현하였다.

s>=e 인 경우 (유효한 경우) 에는 배열에 부분합을 add 해준다.

그리고 s 번째 원소를 포함하지 않는 경우 dfs(s+1, e, sum, v) 

s 번째 원소를 포함하는 경우 dfs(s+1, e, sum+arr[s], v) 를 탐색해줘서 부분합을 모두 구해낼 수 있다.

 

메인 함수에서 아래와 같이 사용하여 lv, rv 를 update 할 수 있다.

dfs(0, n / 2, 0, lv);
dfs(n / 2, n, 0, rv);

lv 와 rv 는 각각 0~n/2 ,  n/2~n 까지의 원소들로 만들어 낼 수 있는 부분합이 원소로 담겨있다.

 

이제 어떻게 할까?

 

우리가 해야 할 것은 n 개의 원소 중에서 i 개를 선택해서 더한 것이 c 이하가 되는 경우의 수를 구하는 작업이다.

 

rv 의 원소를 순차 탐색한다. 이때 원소를 ele 라고 하자.

 

ele + lv[i] 가 c 이하가 되는 경우를 모조리 더해주면 되지 않을까?

 

이를 효율적으로 수행하기 위해서 이분탐색을 구현하자.

 

먼저 lv 를 정렬한다. (이분 탐색은 배열이 정렬되어 있는 상황에서 적용가능하다.)

 

그리고 rv 의 각각의 원소 ele 에 대하여 ele + lv[mid] 가 c 이하인 경우를 answer 변수에 누적시켜주면 된다.

 

Collections.sort(lv);
long ans = 0;
for (long ele : rv) {
    if (ele > c)
        continue;
    int left = 0;
    int right = lv.size();
    int mid = 0;
    while (left < right) {
        mid = (left + right) / 2;
        if(ele + lv.get(mid) > c)
            right = mid;
        else
            left = mid+1;
    }
    ans += right;
}

 

이분 탐색은 항상 헷갈린다..

 

이분 탐색은 조만간 한번 게시물로 정리해야겠다.

 

전체 코드는 아래와 같다.

 

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

public class Main {

    static int n;
    static int c;
    static int[] arr;
    static ArrayList<Long> lv = new ArrayList<>();
    static ArrayList<Long> rv = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;

        stk = new StringTokenizer(br.readLine());
        n = Integer.parseInt(stk.nextToken());
        c = Integer.parseInt(stk.nextToken());
        arr = new int[n];

        stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(stk.nextToken());
        }
        dfs(0, n / 2, 0, lv);
        dfs(n / 2, n, 0, rv);

        Collections.sort(lv);
        long ans = 0;
        for (long ele : rv) {
            if (ele > c)
                continue;
            int left = 0;
            int right = lv.size();
            int mid = 0;
            while (left < right) {
                mid = (left + right) / 2;
                if(ele + lv.get(mid) > c)
                    right = mid;
                else
                    left = mid+1;
            }
            ans += right;
        }
        bw.write(ans+"\n");
        bw.flush();
        bw.close();
    }

    private static void dfs(int s, int e, long sum, ArrayList<Long> v) {
        if (s >= e) {
            v.add(sum);
            return;
        }
        dfs(s + 1, e, sum, v);
        dfs(s + 1, e, sum + arr[s], v);
    }
}

---

참고

https://killerwhale0917.tistory.com/5

Meet in the middle / 중간에서 만나기