취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1208번 문제인 부분수열의 합 2이다.
문제는 아래 링크를 확인하자.

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

2^20의 값이 대충 100만이므로, 주어진 정수를 두개의 집합으로 나누어 가능한 부분수열의 합을 모두 구하고 다시 합치는 Meet in the Middle 전략으로 이 문제를 해결할 수 있다.

각 집합에서 나올 수 있는 부분수열의 합은 약 100만가지이고, 나올 수 있는 각 합을 정렬한 뒤 보관하면 각 집합의 부분수열의 개수에 비례한 선형시간으로 답을 구해낼 수 있기 때문이다.

이때, 각 집합에 담은 부분수열의 합들 중에도 구하는 합과 일치하는 값이 있을 수 있다는 점에 유의하자.

아래는 제출한 소스코드이다.

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

int arr[40];

vector<int> sum1, sum2;

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

	int N, S; cin >> N >> S;
	for (int i = 0; i < N; i++) cin >> arr[i];

	if (N == 1) {
		if (arr[0] == S) cout << 1;
		else cout << 0;
		return 0;
	}

	int mid = N / 2;
	long long sum1cnt = 0;
	if (arr[0] == S) sum1cnt++;
	sum1.push_back(arr[0]);
	for (int i = 1; i < mid; i++) {
		int current = arr[i];
		int vecsize = sum1.size();
		for (int k = 0; k < vecsize; k++) {
			int temp = current + sum1[k];
			if (temp == S) sum1cnt++;
			sum1.push_back(temp);
		}
		if (current == S) sum1cnt++;
		sum1.push_back(current);
	}

	long long sum2cnt = 0;
	if (arr[mid] == S) sum2cnt++;
	sum2.push_back(arr[mid]);
	for (int i = mid + 1; i < N; i++) {
		int current = arr[i];
		int vecsize = sum2.size();
		for (int k = 0; k < vecsize; k++) {
			int temp = current + sum2[k];
			if (temp == S) sum2cnt++;
			sum2.push_back(temp);
		}
		if (current == S) sum2cnt++;
		sum2.push_back(current);
	}

	sort(sum1.begin(), sum1.end());
	sort(sum2.begin(), sum2.end());

	long long ans = 0;
	auto sum1pt = sum1.begin();
	auto sum2pt = sum2.rbegin();
	int sum1size = sum1.size(), sum2size = sum2.size();
	while (sum1pt !=sum1.end() && sum2pt != sum2.rend()) {
		int L = *sum1pt, R = *sum2pt, LR = L + R;
		if (LR > S) sum2pt++;
		else if (LR < S) sum1pt++;
		else {
			long long cntL = 0, cntR = 0;
			while (sum1pt != sum1.end()) {
				if (*sum1pt != L) break;
				cntL++;
				sum1pt++;
			}
			while (sum2pt != sum2.rend()) {
				if (*sum2pt != R) break;
				cntR++;
				sum2pt++;
			}
			ans += cntL * cntR;
		}
	}

	cout << ans + sum1cnt + sum2cnt;
}