Meet In The Middle (중간에서 만나기) MITM 테크닉

MITM이라고도 불리우는 Meet In The Middle 기법은

많은 연산을 줄이기 위해 발명된 테크닉이다.

MITM의 과정

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

이 문제를 풀려고 할 때 모든 무게의 조합의 개수는

$2^N$ 개 이므로 $(2^{30}\approxeq\;1e9)$ TLE가 난다.

이때 연산량을 줄이기 위해 MITM 기법을 사용하는 것이다.

먼저 배열을 두 개로 나눈 후 두 개의 배열에서 나올 수 있는

합을 모두 구해준다. $O(2^{\frac N2})$

구해준 두 배열 중 배열 하나를 정렬하고,

정렬하지 않은 배열을 훑어가며

두 배열의 두 원소의 합이 $C$ 보다 작은 것이 될 수 있는지

판단해주면 된다.

이때 이분탐색을 사용해 합이 $C$ 보다 작은지 판단해주면 된다.

코드는 다음과 같다.

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

int n;
ll r;
vector<ll> a,b,c,d;

void solve(int idx, ll cs, vector<ll> &e, vector<ll> &f){
    for(int i=idx+1;i<e.size();i++){
        cs+=e[i];
        f.push_back(cs);
        solve(i,cs,e,f);
        cs-=e[i];
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> r;
    a.resize(n/2);
    b.resize(n/2+n%2);
    for(ll &t:a) cin >> t;
    for(ll &t:b) cin >> t;
    solve(-1,0,a,c);
    solve(-1,0,b,d);
    sort(d.begin(),d.end());
    ll res=1;
    for(ll &t:c) res+=upper_bound(d.begin(),d.end(),r-t)-d.begin();
    for(ll &t:c) res+=(t<=r);
    for(ll &t:d) res+=(t<=r);
    cout << res;
    return 0;
}

위와 같이 MITM를 사용하면 보통 시간복잡도를 $O(2^N)$ 에서

$O(N\times logN\times2^{\frac N2})$ 으로 줄일 수 있다.