Boj 7453 & 1450 c++ MITM 알고리즘

**Meet in the middle 이란? **

 

쉽게 말해 완전탐색을 하는 것이 힘들 때, 범위를 두개로 나누어 탐색하여 시간복잡도를 획기적으로 줄이는 기법이다.

이때, 범위를 나눌 때에는 딱 절반으로 나누었을 때 가장 효율적으로 작동하기에 '중간'에서 만나기라는 이름이 붙은 것 같다.

(아마도?)

 

예시를 통해 설명해보겠다.

 

40개의 원소를 가진 집합에 대해서 모든 원소의 합이 K를 만족하는 부분집합의 개수를 찾는다고 가정해보자.

우선 하나의 원소당 2가지 경우가 적용되므로 완전탐색 시 탐색 범위는 2^40 = 1,099,511,630,000 (약 1조)....

 

꼭 원소의 개수가 40개가 아니더라도 시간복잡도는 O(2^n)으로 굉장히 크다.

 

고로, 특정 값을 찾는 것을 목표로 할 때에는 모든 경우의 수를 고려하는 것이 비효율적이라는 것을 알 수 있다.

때문에, 우리는 여기서 중간에서 만나기 알고리즘을 적용할 수 있다.

 

집합의 40개 원소를 20개, 20개 씩 나눈 뒤, 각각을 A, B라고 이름을 붙이자.

 

그리고 A의 부분집합의 합의 모든 경우의 수 ( 2^20 = 약 10^6 ) 를 구해, 배열에 저장한 후 정렬한다.

 

마찬가지로 B의 부분집합의 합을 모두 구한다. 찾아야 하는 값은 모든 원소의 합이 K인 경우의 수이기에, B에 저장된 각각의 값을 val 이라 할 때, A에 저장된 값 중에서 K - val을 만족하는 값의 개수를 찾으면 된다.

 

이 방식의 시간 복잡도는 O(2^(n/2)*(n/2)log(n/2)) 으로, 획기적으로 줄어든 것을 알 수 있다.

 

 

그럼 이제 문제로 들어가보자.

 

합이 0인 네 정수 Gold 2

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

 

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

 

각 배열의 크기는 n으로 같다.      (1 <=  n <= 4000)

 

 

이 문제 또한 평면적으로 생각했을 때의 연산횟수는 (4000^4)... 계산해보지 않더라도 시간초과가 날 것을 예상할 수 있다.

중간에서 만나기를 적용해보자.

 

A와 B를 하나의 그룹으로 묶고, C와 D를 또 하나의 그룹으로 묶어보자.

A와 B를 합한 모든 경우의 수를 배열에 저장 후 정렬.

그리고 배열의 값들 중에서 C와 D의 합과 합쳤을 때 0이 되는 값들을 이분탐색으로 찾아주고 매번 누적하여 합해준다.

 

정답을 출력해주면 끝난다.

 

정답 코드.

 

#include <iostream>
#include <algorithm>
#include <vector>
typedef long long ll;

using namespace std;

int lbs(int n, vector<int>& v) {
    int s = 0, e = v.size(), mid;
    while(s < e) {
        mid = (s + e) / 2;
        if(v[mid] < n) {
            s = mid + 1;
        } else {
            e = mid;
        }
    }
    return s;
}

int ubs(int n, vector<int>& v) {
    int s = 0, e = v.size(), mid;
    while(s < e) {
        mid = (s + e) / 2;
        if(v[mid] <= n) {
            s = mid + 1;
        } else {
            e = mid;
        }
    }
    return s;
}

int main() {
    int n;
    cin >> n;
    vector<int> a, b, c, d, sum;
    ll ans = 0;

    for(int i = 0; i < n; i++) {
        int p, q, r, s;
        cin >> p >> q >> r >> s;
        a.push_back(p);
        b.push_back(q);
        c.push_back(r);
        d.push_back(s);
    }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            sum.push_back(a[i] + b[j]);

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

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            int val = c[i] + d[j];
            ans += ubs(val*-1, sum) - lbs(val*-1, sum);
        }
    }
    cout << ans;
}

 

 

냅색문제 Gold 1

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

 

냅색이 아닌데 제목은 냅색인 특이한 문제이다.

 

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

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

 

n <=30, C <= 10^9, 물건의 무게 <= 10^9

 

냅색이 아닌 이유 : 이전 문제들에서는 특정 용량에서 담을 수 있는 물건의 최대 개수, 특정 개수를 담을 수 있는 용량의 최솟값, 등, 

작은 값에서 큰 값을 구해낼 수 있었다.

하지만 이번에는 각각의 물건을 다른 것으로 보고, 담을 수 있는 '경우의 수'를 묻고 있다.

이는 부분집합의 특징을 띠고 있으며, 중간에서 만나기를 적용하는 문제인지 의심해봐야 한다.

 

논리는 동일하다. 2^30번의 연산을 하기 힘들기 때문에, 두 집합으로 나누어 2^15 *15log15의 연산을 하도록 최적화를 하면된다.

 

이번에는 각각의 절반씩의 합을 구한 후, 이분탐색을 돌릴 때 upper_bound 만 해도 된다. 합이 C - value 이하인 값만을 찾으면 되기에 upper_bound의 인덱스만을 참조하면 되기 때문이다.

 

정답 코드.

 

#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;
using namespace std;

int cost[35];

int ubs(ll n, vector<ll>& v) {
    int s = 0, e = v.size(), mid;

    while(s < e) {
        mid = (s + e) / 2;
        if(v[mid] <= n) {
            s = mid + 1;
        } else {
            e = mid;
        }
    }
    return s;
}

int main() {

    int N, C, mid, ans = 0;

    vector<ll> sum;

    cin >> N >> C;

    mid = N / 2;

    for(int i = 0; i < N; i++) {
        cin >> cost[i];
    }

    for(int i = 0; i < (1 << mid); i++) {
        ll val = 0;
        for(int j = 0; j < mid; j++)
            if((1 << j) & i)
                val += cost[j];
        sum.push_back(val);
    }
    sort(sum.begin(), sum.end());

    for(int i = 0; i < (1 << (N-mid)); i++) {
        ll val = 0;
        for(int j = 0; j < (N-mid); j++)
            if((1 << j) & i)
                val += cost[j+mid];
        ans += ubs(C - val, sum);
    }

    cout << ans;
}