백준 1208 - 부분수열의 합 2

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

1208번: 부분수열의 합 2

부분수열이 꼭 연속한 원소로 이뤄질 필요는 없으니 혼동하지 말자. (내 얘기임)

 

0.

합이 S가 되는 부분수열을 구하는 가장 단순한 방법은 모든 부분 수열을 확인해보는 것이다. 크기 N의 수열에 대해 경우의 수, 즉 부분수열의 수는 2^N개가 존재한다.

 

앞전의 부분수열의 합 1 문제는 N의 크기가 20이기 때문에 2^20, 즉 10^6개만 확인하면 됐기 때문에 모든 경우를 일일히 확인해 문제를 풀 수 있다.

 

다음과 같은 재귀함수를 사용하거나 비트마스킹 기법을 쓰면 된다.

//경우의 수 기록을 위한 해쉬맵
map<int, int> M;

void recursion(int start, int end, int val) {
	if(start > end)
    	M[val]++;
	
    //이번 원소를 선택하는 경우와 선택하지 않는 경우
    recursion(start + 1, end, val);
    recursion(start + 1, end, val + v[start]);
}

1.

하지만 이번 문제는 태생부터가 다르다. N의 크기가 40이므로 가능한 경우의 수는 10^12나 된다. 일일히 계산하는 건 불가능하므로 다른 방법을 찾아야 한다. 여기서 사용하는 방법이 분할정복의 일종인 '중간에서 만나기 (MITM, meet in the middle)' 기법이다.

 

먼저 수열을 딱 한 번만 반으로 나누자. 반으로 나눈 수열을 L, R이라고 할때, 위와 비슷한 재귀함수를 이용해 L과 R 각각의 부분수열의 합을 모두 구해 서로 다른 해쉬맵 Ml, Mr에 저장한다.

 

예제 입력에 대해서는 이런 결과를 얻을 수 있을 것이다.

L = {-7, -3, -2}
Ml = {-12, -10, -9, -7, -5, -3, -2, 0}

R = {5, 8}
Mr = {0, 5, 8, 13}

 

2.

이제 중간에서 만날 차례이다. Ml의 모든 키에 대하여 더해서 S가 되는 Mr의 키를 찾는다. Ml의 키를 a, 찾는 키를 b라 하면 a + b = S, 즉 b = -a + S인 b를 찾으면 된다. 이때 키 a, b에 해당하는 값 Ml[a], Mr[b]은 각각 L, R에서 합이 a, b가 되는 모든 경우의 수이므로, a와 b를 더해 S가 되는 경우의 수는 이 둘을 곱한 Ml[a] * Mr[b]이다.

 

그리고 만약 S가 0일 경우, 결과값에 L과 R에서 아무것도 선택하지 않는 경우가 포함될 수 있다. 이 때는 부분수열의 크기가 양수가 아니므로 답에서 제외해야 한다.

소스 코드

vector<int> v;

void recursion(int start, int end, int val, map<int, int>& M) {
	if (start > end) {
		M[val]++;
		return;
	}

	recursion(start + 1, end, val, M);
	recursion(start + 1, end, val + v[start], M);
}

int main() {
	FASTIO;

	int N, S;
	cin >> N >> S;

	v.resize(N);
	for (int& i : v)
		cin >> i;

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

	map<int, int> L, R;
	
    //반으로 나눠 L과 R 해쉬맵을 각각 완성
	recursion(0, N / 2 - 1, 0, L);
	recursion(N / 2, N - 1, 0, R);
	
    //나올 수 있는 최댓값은 2^40 - 1
	long long res = 0;
	if (!S) res--;

	for (auto p : L)
    	//Ml[a] * Mr[b], b = -a + S
		res += 1ll * p.second * R[-p.first + S];

	cout << res << endl;
}