1 번째 시도

  • 모든 input의 부분집합을 구하면 $O(2^N)$인데 N은 최대 40이므로, 시간초과가 발생할 거라고 생각했다.
  • input을 2개의 집합으로 분리한다.
  • 2개의 집합에서 각각의 부분 집합에 대한 sum을 map에 저장한다.
    • 부분집합은 bitmasking을 이용했다. => $O(2^{\frac{N}{2}} \times {\frac{N}{2}})$
  • aMap을 순회하면서 bMap을 bsearch로 구하려 했으나 시간 초과가 발생하였다.
    • $O(2^{\frac{N}{2}} \times log2^{\frac{N}{2}})$여서 될거라고 생각했는데..
    • map의 값을 vec로 복사하는 시간이 오래 걸리나..
  • 구해야할 값이 0이면 공집합인 경우의 수 1을 빼주어야 한다.


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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61



int N, S, A, B;
int a[MAX_N], b[MAX_N];
map<int, int> aMap, bMap;
vector<pair<int, int> > bVec;

int bsearch(int subSum) {
	int left = 0;
	int right = bVec.size()-1;
	while (left <= right) {
		int mid = (left + right) / 2;
		int curSum = bVec[mid].first + subSum;
		if (curSum == S) return bVec[mid].second;
		else if (curSum < S) left = mid + 1;
		else right = mid - 1;
	}
	return 0;
}


ll solution() {
	for (int bitmask = 0; bitmask < 1 << A; bitmask++) {
		int sum = 0;
		for (int digit = 0; digit < X; digit++)
			if ((bitmask & 1 << digit) > 0) sum += a[digit];
		aMap[sum]++;
	}
	for (int bitmask = 0; bitmask < 1 << B; bitmask++) {
		int sum = 0;
		for (int digit = 0; digit < Y; digit++)
			if ((bitmask & 1 << digit) > 0) sum += b[digit];
		bMap[sum]++;
	}

	map<int, int>::iterator it;
	for (it = bMap.begin(); it != bMap.end(); it++) {
		int sum = it->first;
		int cnt = it->second;
		bVec.push_back(make_pair(sum, cnt));
	}
	sort(bVec.begin(), bVec.end());
	
	ll res = 0;
	for (it = aMap.begin(); it != aMap.end(); it++) {
		int aSum = it->first;
		int aCnt = it->second;

		res += ((ll)aCnt * bsearch(aSum));
	}
	return res;
}

int main() {
	scanf("%d%d", &N, &S);
	A = N/2; B = 0;
	int i = 0;
	for (; i < X; i++) scanf("%d", &a[i]);
	for (; i < N; i++) scanf("%d", &b[B++]);
	
	ll ret = solution();
	printf("%lld\n", S == 0? ret - 1 : ret);
}

2 번째 시도

  • input을 2개의 집합(A, B)으로 분리한다.
  • 2개의 집합에서 각각의 부분 집합에 대한 sum을 vector에 저장한다.
    • 부분집합은 bitmasking을 이용했다. => $O(2^{\frac{N}{2}} \times {\frac{N}{2}})$
  • 집합 A의 vector는 오름차순, 집합 B의 vector는 내림차순으로 정렬한다.
  • 다음과 같은 규칙으로 계산을 한다.
    • aSum[i] + bSum[j] == S
      • $(aSum[i]와 같은 값을 가진 원소 개수) \times (bSum[j]와 같은 값을 가진 원소 개수)$
      • i++, j++
    • aSum[i] + bSum[j] < S
      • i++
    • aSum[i] + bSum[j] > S
      • j++
  • 구해야할 값이 0이면 공집합인 경우의 수 1을 빼주어야 한다.


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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70



#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <functional>
#include <string>
#include <climits>
#include <cmath>
#include <map>

using namespace std;

#define MAX_N 42
#define ll long long

int N, S, A, B;
int a[MAX_N], b[MAX_N];
vector<int> aVec, bVec;

ll solution() {
	for (int bitmask = 0; bitmask < 1 << A; bitmask++) {
		int sum = 0;
		for (int digit = 0; digit < X; digit++)
			if ((bitmask & 1 << digit) > 0) sum += a[digit];
		aVec.push_back(sum);
	}
	for (int bitmask = 0; bitmask < 1 << B; bitmask++) {
		int sum = 0;
		for (int digit = 0; digit < Y; digit++)
			if ((bitmask & 1 << digit) > 0) sum += b[digit];
		bVec.push_back(sum);
	}

	sort(aVec.begin(), aVec.end());
	sort(bVec.begin(), bVec.end(), greater<int>());
	
	ll res = 0;
	int i = 0, j = 0;
	while (i < aVec.size() && j < bVec.size()) {
		int aSum = aVec[i];
		int bSum = bVec[j];
		if (aSum + bSum == S) {
			int aCnt = 1, bCnt = 1;
			i++; j++;
			while (i < aVec.size() && aSum == aVec[i]) {
				i++; aCnt++;
			}
			while (j < bVec.size() && bSum == bVec[j]) {
				j++; bCnt++;
			}
			res += (ll)aCnt * bCnt;
		} 
		else if (aSum + bSum < S) i++;
		else j++;
	}
	return res;
}


int main() {
	scanf("%d%d", &N, &S);
	A = N/2; B = 0;
	int i = 0;
	for (; i < X; i++) scanf("%d", &a[i]);
	for (; i < N; i++) scanf("%d", &b[B++]);
	
	ll ret = solution();
	printf("%lld\n", S == 0? ret - 1 : ret);
}