백준1208 부분수열의 합2

작성일 | In

문제 링크

  • http://icpc.me/1208

사용 알고리즘

  • meet in the middle

시간복잡도

  • O(2N/2 log N)

풀이

2N 완전탐색을 돌리면 당연하게도 TLE가 납니다. 절반씩 나누어봅시다.

먼저 왼쪽 절반에 대해 모든 부분집합의 합을 구해줍시다. O(2N/2)가 걸립니다. 결과는 map에 mp[num] = cnt 형태로 저장을 합시다.

오른쪽 절반으로 만들 수 있는 부분집합의 합을 i라고 합시다. 모든 i에 대해 mp[s-i]의 합을 구해주면 문제의 정답을 구할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

vector<int> v;
int n, s, half;
long long ans;
map<int, int> mp;

void dfsLeft(int idx, int sum){
	if(idx == half){
		mp[sum]++; return;
	}
	dfsLeft(idx+1, sum);
	dfsLeft(idx+1, sum + v[idx]);
}

void dfsRight(int idx, int sum){
	if(idx == n){
		ans += mp[s-sum]; return;
	}
	dfsRight(idx+1, sum);
	dfsRight(idx+1, sum + v[idx]);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> s;
	half = n/2; v.resize(n);
	for(int i=0; i<n; i++) cin >> v[i];
	dfsLeft(0, 0);
	dfsRight(half, 0);
	if(s == 0) ans--;
	cout << ans;
}