[BAE/<JOON> 문제풀이] 1208. 부분 수열의 합 2

핵심::
MEET IN THE MIDDLE 개념 문제

풀이::
MEET IN THE MIDDLE 알고리즘은 1보다 큰 N에 대해 N^M 보다 N^(M/K) * K 가 더 작다는 아이디어로 만들어진 분할 정복의 일종이다.

숫자가 N개 주어질 때 모든 합의 가능 여부를 체크하려면 경우의 수가 2^N가지 있다. 

2^40은 1,099,511,627,776 이므로 주어진 40개의 숫자를 전수 검사하는 방식으로는 시간 안에 해결 할 수 없다.

20개씩 나눠 첫 세트에 대해 전수 검사를 진행하고 S - 숫자 의 값이 두번째 세트에서 가능하다면 탐색을 종료한다.

탐색하는 S를 만드는 조합이 불가능한 경우가 최악의 경우로 이 때 탐색하는 횟수는 (2^20) * 2 = 2,097,152 이다.

의견::
분할 정복은 쪼개진 문제들을 (N/K)^M의 복잡도로 풀고 나눠진 K개의 문제들을 다시 합치는 과정이 있다는 차이점이 있다고 하는데

MEET IN THE MIDDLE 도 결국 계산한 K개의 문제들을 다시 합치는 과정이 있는데 뭐가 다르다는 건지는 잘 모르겠다. 

쪼갠 순서대로 합치는 부분이 다른건가?

 

코드::

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;
using ull = long long;

ull s1[8000001];

int main()
{
	int n, k;
	cin >> n >> k;
	vector<int> arr(n + 1);
	k += 4000000;
	int t = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &arr[i]);
		t += arr[i];
	}

	int n1 = n / 2;
	for (int i = 0; i < pow(2, n1); i++) {
		int j = i;
		int sum = 4000000;
		int cnt = 0;
		while (j > 0) {
			cnt++;
			if (j % 2 == 1) {
				sum += arr[cnt];
			}			
			j /= 2;
		}		
		s1[sum]++;
	}
		
	ull dap = 0;
	
	for (int i = 0; i < pow(2, n - n1); i++) {
		int j = i;
		int sum = 0;
		int cnt = n1;
		while (j > 0) {
			cnt++;
			if (j % 2 == 1) {
				sum += arr[cnt];
			}
			j /= 2;
		}
		if (k - sum < 0) continue;
		dap += s1[k - sum];
	}
	if (k == 4000000) dap -= 1;
	cout << dap;
	return 0;
}