반응형
1208번: 부분수열의 합 2
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
www.acmicpc.net
|
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
|
#include <iostream>
#define rep(i,n) for(ll i=0;i<n;i++)
#define ll long long
using namespace std;
ll arr[41], a1[4000001], a2[4000001];
ll n, s, ans;
void calc() {
ll mask = 0;
ll tmp = 0;
ll len = n / 2;
// 배열 왼쪽
while (mask < (1 << len)) {
tmp = 0;
rep(i, len)
tmp += ((mask >> i) & 1)* arr[i];
a1[tmp + 2000000]++;
mask++;
}
// 배열 오른쪽
mask = 0;
if (n % 2 == 1)
len++;
while (mask < (1 << len)) {
tmp = 0;
rep(i, len)
tmp += ((mask >> i) & 1)* arr[i + n / 2];
a2[tmp + 2000000]++;
mask++;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> s;
rep(i, n)
cin >> arr[i];
// 1. 배열 나눠서 부분수열 계산
calc();
// 2. 투 포인터로 탐색
ll p1 = 0, p2 = 4000000;
if (s == 0)
ans--;
s += 4000000;
while (1) {
while (p1 + p2 > s) // s보다 크면 p2를 이동시켜서 더 작게 만들기
p2--;
while (p1 + p2 < s) // s보다 작으면 p1을 이동시켜서 더 크게 만들기
p1++;
if (p1 > 4000000 || p2 < 0) break; // 범위 벗어나면 종료
if (p1 + p2 == s) // s와 같으면 더하기
ans += a1[p1] * a2[p2];
p1++; // 다음 탐색 진행을 위해 p1 오른쪽으로 이동
}
cout << ans;
}
|
cs |
반응형