[BOJ/C++] 1208(부분수열의 합2)

1. Link

https://www.acmicpc.net/problem/1208
비슷한 문제(부분수열의 합): https://www.acmicpc.net/problem/1182

• 사실 이분 탐색이라기보다 dfs에 가까운 풀이같지만.. 이 방법 외에는 별다른 방법이 생각이 안 났습니다.

2. 풀이 과정

1. 크기 양수인 부분수열 중 전부 합한 값이 s가 되는 경우의 수 -> 재귀적 풀이
2. n <= 40 -> 단순 재귀로는 2^40 시간초과, 반으로 줄여야함

풀이 순서
1. n을 최대 40으로 계산할 때, 왼쪽과 오른쪽으로 반 나눠 각 계산이 2^20까지 되도록 합니다.
2. 왼쪽부터 계산해서 나온 모든 값을 map 자료구조에 넣어주도록 합니다.
3. 오른쪽에 대한 연산 값 중 s - sum을 통해 합산 s가 되는 경우의 수를 map에서 꺼내 결과값에 더해줍니다.
4. s == 0일 경우 {}이라는 공집합 발생이 가능하니, 굳이 count하지 않는 선이라면 결과값에서 1을 제외해줍니다.

• 예제를 들어 문제를 설명해보도록 하겠습니다.
  

1. 왼쪽과 오른쪽을 각각 두 배열로 인지합니다(실제 나누기엔 굳이 메모리 낭비이므로, mid = n >> 1로 대체)
   

2. 왼쪽에서 나올 수 있는 모든 경우의 수를 map에 대입합니다.
   

3. s - sum의 값을 map에서 찾아 꺼내줍니다. 다음의 자료에서는 -3과 0이 조건을 만족함을 확인할 수 있습니다.
   

4. 다만 0은 공집합이므로 제거해줍니다. 따라서 왼쪽 {-3}, 오른쪽 {5, -2}인 경우만 가능하므로 결과는 1을 출력합니다.

3. 정답 코드

#include<iostream>
#include<map>

using namespace std;

int n, s, mid;
long long answer = 0;
int a[40];
map<int, int> m;

void input() {
	cin >> n >> s;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	mid = n >> 1;
}

void leftSum(int cur, int sum) {
	if (cur == mid) {
		++m[sum];
		return;
	}
	leftSum(cur + 1, sum);
	leftSum(cur + 1, sum + a[cur]);
}

void rightSum(int cur, int sum) {
	if (cur == n) {
		answer += m[s - sum];
		return;
	}
	rightSum(cur + 1, sum);
	rightSum(cur + 1, sum + a[cur]);
}

void solution() {
	input();
	leftSum(0, 0);
	rightSum(mid, 0);

	if (s == 0) --answer;
	cout << answer;
}

int main() {
	cin.tie(0), cout.tie(0);
	ios_base::sync_with_stdio(0);
 	solution();
	return 0;
}