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

이 문제는 n이 30이고 무게가 10^9이다.

완탐으로 하기에는 담고 안 담고 2^30 -> 10억이라서 너무 큰 수이다.

dp로 저장하기에는 상태값이 [30][10^9]라서 값이 너무 크다.

완탐이나 DP도 안될 때

즉, n이 너무 클 때 반으로 쪼개서 각각 완탐을 하는 게 meet in the middle 알고리즘이다. 

완전 탐색 (Brute-force): O(2ⁿ) → n ≤ 30일 때 너무 큼 ❌
Meet in the Middle: O(n * 2ⁿ/²) → n ≤ 30에서 현실적으로 가능 ✅

이분탐색을 하는 것도 아니다.

각각 완탐을 한 다음에 경우의 수를 더할 뿐이다.

2의 30승인 10억이 넘는데

절반으로 나누면 O(2^(n/2)) 이므로 2의 15승은 32,768 이다.

각각을 완탐하고 나올 수 있는 모든 최종 무게의 경우의 수를 나열하고 정렬한다.

아무것도안 담는 경우를 포함한 0 ~ 모든 것을 담은 경우의 수의 숫자들이 생기는데,

A를 순회하면서 이렇게 담았을 때 남은 무게만큼 B에서 담는 경우를 더하면 끝. 

이때는 upper_bound 함수를 활용하는데, 내부적으로 upper_bound는 이진탐색(logN) 을 실행하므로

O(2^(n/2) * log(2^(n/2)))

= O(2^(n/2) * (n/2))

= 2^15 * 15

= 491,520

0도 포함되기 때문에 A 쪽에서 꽉 찼어도 B에서 0으로 경우의 수가 +1 되기 때문에 무게는 별도 고려 안 해도 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, c, w[31];
vector<int> v, v2;

void Go(int here, int end, vector<int> &v, int sum)
{
    if (sum > c) 
        return;

    if (here > end)
    {
        v.push_back(sum);
        return;
    }

    Go(here + 1, end, v, sum + w[here]); // 담는 경우
    Go(here + 1, end, v, sum); // 안담는 경우
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> c;

    for (int i = 0; i < n; ++i)
        cin >> w[i];

    Go(0, n / 2 - 1, v, 0);
    Go(n / 2, n - 1, v2, 0);
    
    sort(v.begin(), v.end());
    sort(v2.begin(), v2.end());

    int ret = 0;
    for (int i : v)
    {
        // 다른 주머니의 모든 가능한 경우의 수와 합친다.
        int max_addWeight = c - i;
        ret += ((int)(upper_bound(v2.begin(), v2.end(), max_addWeight) - v2.begin()));
    }

    cout << ret;
}

따지고 보면 시간복잡도가 O(n * 2^(n/2)) 로 비교적 빠를 뿐이지

그리 빠른 알고리즘은 아니기 때문에 n 이 30까지는 충분하지만 n이 40을 넘어가면 사용하기에 무리가 있다고 한다.