[백준]1208번 부분수열의 합 2 - C++

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

1208번: 부분수열의 합 2

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

---

     N 이 40이었기 때문에 하나 씩 확인하며 가능 여부를 판단하려면 O(2^40)으로 시간 초과가 나게 된다. 그래서 반으로 나누어서 2^20 * 2로 만든다면 1024 *1024 * 2 정도로 약 2'000'000 정도로 충분히 시간제한 안에 들어올 수 있게 된다. 그래서 Map을 활용하여 Key 값을 부분 수열의 합, Value 값을 해당 Key 값을 만들 수 있는 부분 수열의 개수로 설정하여 왼쪽 부분의 경우 개수를 저장을 하고 오른쪽 수열의 경우 구한 부분 수열의 합이 sum 이면 map[S-sum]의 값 즉, 왼쪽 부분 수열의 합이 S-sum이었던 값들과 더하면 S 가 만들어지게 되므로 결과값에 map[S-sum]의 값을 더하면 된다. 이때 S가 0이라면 둘 다 공집합인 경우는 최종 결과값에 포함이 안되므로 1을 제외해준다. 

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int N, S;
int arr[41];
map<int, int> total;
long long cnt;

void left(int s, int sum) {
	if (s == N / 2) {
		total[sum]++;
		return;
	}
	left(s + 1, sum);
	left(s + 1, sum + arr[s]);
}

void right(int s, int sum) {
	if (s == N) {
		cnt += total[S-sum];
		return;
	}
	right(s + 1, sum);
	right(s + 1, sum + arr[s]);
}

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

	cin >> N >> S;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	left(0, 0);
	right(N / 2, 0);
	
	if (S == 0) cout << cnt - 1;
	else cout << cnt;
	return 0;
}

---

    처음에 2^40이라는 것을 생각하고 O(NlogN) 과 같이 정렬하여 이분 탐색을 활용하여야 하나 생각을 해보았다. 하지만 생각을 해보아도 어떻게 이분 탐색을 통하여 구할지 생각이 잘 나지 않았다. 그래서 검색을 한 결과 그냥 반으로 나눈 뒤 왼쪽과 오른쪽의 합을 더하는 것이었다. 마무리로 모두가 공집합인 경우도 생각해야 했다. N 이 40이었던 것이 반으로 나누는 힌트였던 것 같다. 이렇게 2^N을 해결하기 위해 N을 이등분하는 것을 생각해내지는 못했지만 다음에 40 근방의 숫자를 보면 생각해낼 수 있을 것 같다!