밋 인더 미들 (Meet in the middle, 중간에서 만나기) 알고리즘 (백준 BOJ 1450)

밋 인더 미들(Meet in the middle, 또는 중간에서 만나기) 알고리즘은 한 개의 그룹으로 완전 탐색을 하지 못하는 경우 두 개의 그룹으로 나누어 탐색하여 그 결과를 확인하여 시간을 줄이는 알고리즘입니다. (ex : O(2^N) → O(2 × 2^(N/2)))

 

 

백준 BOJ 1450 : 냅색문제

구체적인 예시를 들기 위해 백준 BOJ 1450번 문제인 '냅색문제'를 풀이하며 설명해보도록 하겠습니다.

문제를 요약해보면, N개의 물건 각각 무게를 가지고 있고 최대 C만큼의 무게를 넣을 수 있는 가방에 물건들을 넣는 방법의 수를 구하는 문제입니다.

 

 

 

물건의 수가 최대 30개이고 각 물건은 가방에 넣는다 vs 안 넣는다의 두 가지 선택지가 있으므로 모든 경우의 수를 따지면 최대 2^30의 연산이 필요합니다.

이는 대충만 계산해봐도 시간 제한 안에 풀이가 불가능한 수치임을 알 수 있으므로, 다른 방법을 찾아야합니다.

 

밋 인더 미들(meet in the middle) 알고리즘을 사용하여 풀이를 해보면, 0 ~ N/2번째 원소까지를 그룹 A로 N/2 + 1 ~ N번째 원소까지를 그룹 B로 만든 다음 그룹 A의 각 원소에 대해 합이 C 이하의 크기를 가지는 그룹 B의 원소 수를 합하여 답을 구하면 됩니다.

그룹 A와 그룹 B의 원소를 구하는데 걸리는 시간은 각각 O(2^(N/2))이므로 최대 2^15 = 65,536 정도의 연산이 필요하므로 여유있게 통과 가능합니다.

또한 마지막에 경우의 수를 counting 해주는 과정에서는 2^(N/2)에다가 B의 정렬된 원소를 이분탐색 하므로 log(2^(N/2)) ≒ N, 즉 곱해주면 O(N × 2^(N/2)) 정도로 생각할 수 있습니다. (그래봤자 98만 정도로 역시 여유있게 시간 내에 통과할 수 있습니다.

 

 

#include <bits/stdc++.h>
using namespace std;

vector<long long> arr;
vector<long long> setA, setB;

void combine(int Left, int Right, vector<long long>& Set, long long sum) {
    if(Left > Right) {
        Set.push_back(sum);
        return;
    }

    combine(Left + 1, Right, Set, sum);
    combine(Left + 1, Right, Set, sum + arr[Left]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, C; cin >> N >> C;

    arr.resize(N);
    for(int i=0; i<N; i++) cin >> arr[i];

    combine(0, N/2, setA, 0);
    combine(N/2 + 1, N-1, setB, 0);

    sort(setB.begin(), setB.end());

    long long ans = 0;
    for(int i=0; i<setA.size(); i++)
        ans += upper_bound(setB.begin(), setB.end(), C - setA[i]) - setB.begin();

    cout << ans;
}

 

 

백준 BOJ 7453 : 합이 0인 네 정수

밋 인더 미들(Meet in the middle) 알고리즘이 사용되는 다른 문제도 한 번 풀어봅시다.

다음 문제는 백준 BOJ 7453의 합이 0인 네 정수라는 문제의 풀이입니다.

 

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 순서쌍의 개수를 구하는 문제입니다.

이 때 N은 최대 4000이므로, 4000^4의 조합을 모두 해보기에는 시간 초과가 발생할 것입니다.

 

따라서 A와 B를 각각 묶어 4000 * 4000 = 16,000,000개로 이루어진 sum 조합을 만들고, 이를 정렬해준 뒤 이들 중 -C[i]-D[j]의 합을 가지는 sum이 몇 개나 있는지를 upper_bound와 lower_bound를 이용하여 log 시간에 찾아주면 충분히 시간 안에 해결이 가능합니다.

 

 

#include <bits/stdc++.h>
#define MAX 4001
using namespace std;

int arr[4][MAX];
vector<int> sum;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    for(int j=0; j<N; j++)
        for(int i=0; i<4; i++) cin >> arr[i][j];

    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            sum.push_back(arr[0][i] + arr[1][j]);

    sort(sum.begin(), sum.end());

    long long ans = 0;
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++) {
            int temp = arr[2][i] + arr[3][j];
            ans += upper_bound(sum.begin(), sum.end(), -temp) - lower_bound(sum.begin(), sum.end(), -temp);
        }

    cout << ans;
}