중간에서 만나기(MITM; Meet in the Middle) 알고리즘 (C++)

중간에서 만나기(Meet in the Middle)이란?

중간에서 만나기란 완전 탐색에 시간이 오래 걸리는 경우 대상을 두 그룹으로 나누어 탐색하여 시간을 단축하는 방법이다.

 

예를 들어, 크기가 $N$인 집합의 모든 부분 집합을 구하기 위해서는 $O(2^N)$의 시간이 걸린다.

하지만 모든 부분 집합 중 특정 조건을 만족하는 경우를 찾기만 하면 된다면, 집합을 반으로 쪼개 각각 탐색하여 $O(2\times2^{N/2})$만에 해결할 수 있다.

 

MITM 적용해보기

백준 1208번 부분수열의 합 2 문제를 직접 풀어보자.

수열의 부분수열 중 합이 $S$가 되는 경우의 수를 구하는 문제이다.

 

완전 탐색을 위해서는 앞에서 말했듯이 $2^{40} = 1,099,511,627,776$회의 연산이 필요한데, 이는 제한 시간인 1초 내에 수행이 불가하다.

따라서 중간에서 만나기 알고리즘을 사용해야 시간 안에 경우의 수를 구해낼 수 있다.

 

1단계) 절반으로 나누기

먼저 수열을 두 개의 그룹으로 나누어주어야 한다. 크기를 정확히 반으로 나누는 것이 가장 효율적이다.

 

2단계) 그룹A에서 나올 수 있는 모든 경우 구하기

반으로 나눴다면 그룹을 하나 골라 그 안에서 나올 수 있는 모든 경우를 구해 저장해둔다.

위 문제에서는 해당 그룹에서 나올 수 있는 모든 부분수열의 합을 구하면 되겠다.

int middle = n / 2;
vector<int> sums;

for(i = 0; i < (1 << middle); ++i) {
    int value = 0;
    for(j = 0; j < middle; ++j) {
        if(i & (1 << j)) value += arr[j];
    }
    sums.push_back(value);
}

 

3단계) 그룹B에서도 계산하며 답 구하기

위와 같은 과정을 똑같이 그룹B에서도 해주면 된다.

다만 이번에는 값을 저장해두는 것이 아니라 그룹A에서 나온 값을 바탕으로 정답(경우의 수)을 구해내면 된다.

 

위 문제의 경우 이분탐색을 이용해 경우의 수를 구할 수 있다.

그룹A에서 나온 값에서 ($S$ $-$ 그룹B에서 나온 값)을 찾으면 된다. Upper Bound에서 Lower Bound를 빼면 쉽게 개수를 구할 수 있다.

sort(sums.begin(), sums.end()); // 이분탐색을 위한 정렬

long long answer = 0; // int면 Overflow 발생!

for(i = 0; i < (1 << (n - middle)); ++i) {
    int value = 0;
    for(j = 0; j < (n - middle); ++j) {
        if(i & (1 << j)) value += arr[j + middle];
    }
    answer += upper_bound(sums.begin(), sums.end(), s - value) - lower_bound(sums.begin(), sums.end(), s - value);
}

if(s == 0) answer--; // 크기가 0인 부분 수열 제거

cout << answer;

 

최종 코드

#include <bits/stdc++.h>

using namespace std;

int i, j;
int n, s;
int arr[40];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> s;
    
    for(i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    
    // 1단계: 반으로 나눈 후 그룹A에서 합 계산
    int middle = n / 2;
    vector<int> sums;
    
    for(i = 0; i < (1 << middle); ++i) {
        int value = 0;
        for(j = 0; j < middle; ++j) {
            if(i & (1 << j)) value += arr[j];
        }
        sums.push_back(value);
    }
    
    sort(sums.begin(), sums.end()); // 이분탐색을 위한 정렬

    // 2단계: 그룹B 계산하며 경우의 수 구하기
    long long answer = 0; // int면 Overflow 발생!
    
    for(i = 0; i < (1 << (n - middle)); ++i) {
        int value = 0;
        for(j = 0; j < (n - middle); ++j) {
            if(i & (1 << j)) value += arr[j + middle];
        }
        answer += upper_bound(sums.begin(), sums.end(), s - value) - lower_bound(sums.begin(), sums.end(), s - value);
    }
    
    if(s == 0) answer--; // 크기가 0인 부분 수열 제거

    cout << answer;
}

시간 복잡도는 MITM에 의해 $O(2^{N/2})$이다.

 

관련 문제 (BOJ)

• [7453] 합이 0인 네 정수: 부분수열의 합 문제와 더불어 대표적인 MITM 문제
• [1450] 냅색문제
• [1044] 팀 선발: 조건이 조금 까다로워진 심화 문제