백준 1182번 : 부분수열의 합

Meet in the Middle 개념

Meet in the Middle은 주어진 문제를 두 개의 부분 문제로 나누어 해결하는 방식입니다.
완전 탐색을 할 경우, 모든 부분수열을 탐색하면 시간 복잡도가 O(2^N)이지만, Meet in the Middle을 사용하면 두 부분으로 나누어 O(2^(N/2))로 줄일 수 있습니다.

이 방법을 이용하면 시간 복잡도를 획기적으로 줄일 수 있어 N=40 정도까지도 충분히 해결할 수 있습니다.

 

Meet in the Middle을 3개 그룹으로 나누는 경우

보통 2개 그룹으로 나누는 이유는:

• 모든 부분집합을 구하는 데 O(2^N/2) 로 줄일 수 있기 때문입니다.
• 그 후, unordered_map을 이용해 빠르게 대응되는 합을 찾을 수 있기 때문입니다.

하지만,
✅ 3개 그룹으로 나누면 O(2^(N/3)) 로 더 줄일 수 있음
✅ 다만, 탐색 시 2개의 그룹만 조회하던 방식이 3개 그룹을 조회해야 하므로 구현이 복잡해짐

 

시간 복잡도 비교

• 2개 그룹으로 나눌 경우
  → 각 그룹에서 O(2^(N/2)) 만큼 부분집합 합을 저장하고,
  → 탐색이 O(2^(N/2)) 이므로 O(2^(N/2))
• 3개 그룹으로 나눌 경우
  → 각 그룹에서 O(2^(N/3)) 만큼 부분집합 합을 저장하고,
  → 두 개 그룹의 모든 합을 검사해야 하므로 O(2^(2N/3))
  → 따라서, O(2^(2N/3)) 가 됨.

✅ 즉, 3개로 나누면 개별 그룹의 크기는 줄어들지만, 탐색 비용이 커져서 효과가 애매할 수 있음
✅ 보통 NNN이 40 이상으로 클 때, 2개로 나누는 것이 더 효율적이고, 3개로 나누는 것은 특수한 경우에만 유용함.

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

void subsetSum(int start, int end, vector<int>& a, unordered_map<int, int>& m) {
    int n = end - start;
    for (int i = 0; i < (1 << n); i++) {
        int sum = 0;
        for (int j = 0; j < n; j++)
            if (i & (1 << j)) sum += a[start + j];
        m[sum]++;
    }
}

int main() {
    int n, s;
    cin >> n >> s;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    unordered_map<int, int> left, right;
    subsetSum(0, n / 2, a, left);
    subsetSum(n / 2, n, a, right);

    long long cnt = 0;
    for (auto& [sum, freq] : left) {
        if (right.count(s - sum)) cnt += (long long)freq * right[s - sum];
    }
    if (s == 0) cnt--;
    cout << cnt;
}