[백준 1208] 부분수열의 합 2 (C++)

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

문제

---

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

 

입력

---

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

 

출력

---

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

 

문제 풀이

---

이분탐색 문제.

 

N이 최대 40개이므로 그대로 모든 가능한 경우의 수를 구하면 시간초과가 발생한다. 수열을 2개로 나누어 각 수열에서의 가능한 수를 구한다.

사이즈가 N/2인 배열과 나머지가 되는 배열을 만들어 입력을 저장한다. 이후 백트래킹을 이용해 첫번째 배열은 원소가 1개인 경우부터 N/2개인 경우까지 모든 경우의 수를 구하고, 두번째 배열은 원소가 1개인 경우부터 N - N/2개인 경우까지 모든 경우의 수를 구해준다.

 

이후 이분탐색으로 가능한 개수를 찾아주면 된다.

첫번째 배열에서 얻은 모든 경우의 수가 2 2이고, 두번째 배열에서 얻은 모든 경우의 수가 3 3 3 이며, 구하려는 합이 5인 경우, 가능한 경우의 수는 6이다. 즉, 첫번째 배열의 어떤 숫자에 대해 짝이 맞는 숫자가 여러 개 존재할 때 그 숫자의 개수만큼 답이 된다. upper_bound()에서 lower_bound()만큼 빼주면 찾는 값의 개수를 구할 수 있으므로 이를 이용한다.

 

첫번째 배열 +  두번째 배열로도 합을 S를 만들 수 있지만, 첫번째 배열만 사용하거나, 두번째 배열만 사용하는 경우에도 합을 S를 만들 수 있는 경우가 있다. 예를 들어 첫번째 배열에서 얻은 모든 경우의 수가 0이고, 두번째 배열에서 얻은 모든 경우의 수가 0이며, 구하려는 합이 0일 때, 첫번째 배열에서만 1개, 첫번째 배열 + 두번째 배열에서 1개, 두번째 배열에서만 1개를 얻을 수 있다. 다시 말해, 첫번째 배열과 두번째 배열에서 각각 얻은 모든 경우의 수에서 S의 개수만큼을 더해주어야 한다.

 

아래는 코드.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
int* arr1;
int* arr2;
bool* isVisited1;
bool* isVisited2;

vector<int> v1;
vector<int> v2;

void dfs(int depth, int maxDepth, int index, vector<int>& v, int* arr, bool* isVisited, int arrSize, int sum)
{
	if (depth == maxDepth)
	{
		v.push_back(sum);
	}
	else
	{
		for (int i = index; i < arrSize; i++)
		{
			if (isVisited[i] == false)
			{
				sum += arr[i];
				isVisited[i] = true;
				dfs(depth + 1, maxDepth, i+1, v, arr, isVisited, arrSize, sum);
				sum -= arr[i];
				isVisited[i] = false;
			}
		}
	}
}

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

	cin >> N >> M;
	int size1 = N / 2;
	int size2 = N - size1;
	arr1 = new int[size1];
	isVisited1 = new bool[size1];
	arr2 = new int[size2];
	isVisited2 = new bool[size2];
	long long answer = 0;
	for (int i = 0; i < size1; i++)
	{
		cin >> arr1[i];
		isVisited1[i] = false;
	}
	for (int i = 0; i < size2; i++)
	{
		cin >> arr2[i];
		isVisited2[i] = false;
	}
	for (int i = 1; i <= size1; i++)
	{
		dfs(0, i, 0, v1, arr1, isVisited1, size1, 0);
	}
	for (int i = 1; i <= size2; i++)
	{
		dfs(0, i, 0, v2, arr2, isVisited2, size2, 0);
	}
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());
	answer += upper_bound(v1.begin(), v1.end(), M) - lower_bound(v1.begin(), v1.end(), M);
	for (int i = 0; i < v1.size(); i++)
	{
		int counts = upper_bound(v2.begin(), v2.end(), M - v1.at(i)) - lower_bound(v2.begin(), v2.end(), M - v1.at(i));
		answer += counts;
	}
	answer += upper_bound(v2.begin(), v2.end(), M) - lower_bound(v2.begin(), v2.end(), M);
	cout << answer << "\n";
	return 0;
}