BOJ : https://www.acmicpc.net/problem/1208
github : https://github.com/junho0956/Algorithm/blob/master/1208/1208/%EC%86%8C%EC%8A%A4.cpp
이 문제를 풀기 전에는 기본적으로 집합의 합의 경우를 구해내는 문제인
1182번 부분수열의 합 https://junho0956.tistory.com/16을 풀어보시면 좋습니다.
부분수열의 합2 문제는 1182번 과는 다르게 범위가 2배 늘어난 문제입니다.
기본적으로 N 이 20이면 백만정도의 범위가 나오는데, N 이 40이 되면 1조가 넘는 계산량이 나오기 때문에
1182번과 같은 방식으로 풀면 시간초과가 날 수 밖에 없습니다.
이 문제를 해결하기 위해서는 N이 40인 배열을 반으로 나누는 계산이 필요합니다.
그럼 N이 20인 배열을 2번 계산하면 되기때문에 계산량이 확 줄게되어 문제를 해결할 수 있게 됩니다.
반으로 쪼갠 배열들의 이름을 A,B 라고 했을 때
원하는 답인 경우의 수는 3가지 방법으로 접근할 수 있습니다.
1. A의 부분집합의 합 중에서 S를 만들 수 있는 경우
2. B의 부분집합의 합 중에서 S를 만들 수 있는 경우
3. A와 B의 부분집합의 합 중에서 A+B로 S를 만들 수 있는 경우
1,2번 방법은 부분집합의 합을 만드는 과정에서 1182번 문제와 같이 경우의 수를 구해주시면 됩니다.
3번 방법은 S를 A+B로 만들어야하기때문에
A[i] 로 S를 만들기 위해서는 B에서 S-A[i] 가 존재해야한다는 것을 알 수 있습니다.
이를 이용해서, S-A[i] 를 미리 계산해둔 후에 B의 합의 집합내에서 S-A[i] 를 찾아주시면 됩니다.
이분탐색을 이용해서 그 범위를 빠르게 찾아주시면 됩니다.
lower_bound => 원하는 키값과 같은 값들의 첫번째 위치 또는 키값이 없을때는 키값보다 첫번째로 큰 위치
(ex : 223335566 에서 lower_bound 3 은 인덱스 2)
upper_bound => 원하는 키값 기준 처음으로 큰 위치
(ex : 223335566 에서 lower_bound 3,4 은 인덱스 5)
S-A[i] 라는 것은 같은 값이 여러개가 존재할 수도 있고, 없을수도 있고, 단 하나만 있을 수도 있습니다.
결국 upper_bound 값 - lower_bound 값을 하게 되면 원하는 S-A[i] 의 값들의 갯수를 알 수 있습니다.
이렇게 3번 방법으로 경우의 수를 구하시면 됩니다.
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
|
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int arr[40];
int N, S;
long long cnt;
vector<int> a, b;
void makeA(int idx, int sum) {
sum += arr[idx];
if (idx >= N / 2) return;
// 만약 S를 만들 수 있다면 cnt++을 해준다
if (sum == S) cnt++;
a.push_back(sum);
makeA(idx + 1, sum - arr[idx]);
makeA(idx + 1, sum);
}
void makeB(int idx, int sum) {
sum += arr[idx];
if (idx >= N) return;
// 만약 S를 만들 수 있다면 cnt++을 해준다
if (sum == S) cnt++;
b.push_back(sum);
makeB(idx + 1, sum - arr[idx]);
makeB(idx + 1, sum);
}
int main() {
cin >> N >> S;
for (int i = 0; i < N; i++) cin >> arr[i];
// 벡터 a,b 에 반으로 나눈 각 배열에 대한 만들 수 있는 모든 부분집합의 합들을 미리 구해놓는다
makeA(0, 0);
makeB(N / 2, 0);
// 이분탐색을 이용하기 위해서 미리 정렬을 해둔다
sort(a.begin(), a.end());
sort(b.begin(), b.end());
// 찾고자하는 값의 갯수를 이분탐색을 이용해서 구한다
for (int i = 0; i < a.size(); i++) {
int temp = S - a[i];
int lower = lower_bound(b.begin(), b.end(), temp) - b.begin();
int upper = upper_bound(b.begin(), b.end(), temp) - b.begin();
cnt += upper - lower;
}
cout << cnt;
return 0;
}
|