문제
풀이
난이도가 있는 문제이다. Reference에서 참조한 코드를 첨부한다. 이 문제는 물건의 개수 N이 30이여서, 전체 물건들을 넣고 안넣고의 경우의 수 2^30의 연산 횟수가 필요하다. 이는 시간 초과로 이어져 이를 해결하기 위해 투 포인터를 이용해 해결한다. 먼저, A그룹(0~N/2-1), B그룹(N/2~N) 두 그룹으로 물건들을 나눈다. 그 이후 각각의 경우의 수들을 계산하여, 배열에 넣는다. 최대 2^15 번의 계산을 총 2회씩 하므로 2^16의 연산이 진행된다. 그 이후 시간을 줄이기 위해, B그룹을 오름차순으로 정렬한 뒤, binarysearch를 통해 A그룹의 i번째 sum 값과 B그룹의 sum 값이 C이하인 값을 찾는다. 마지막으로 탐색된 값이 곧 경계가 되어 ans 변수에 A그룹의 i번째 sum으로 만들 수 있는 B그룹의 경우의 수만큼을 계속 더해주어, 최종 결과를 출력한다.
소스 코드
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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, C, asize, bsize, idx;
int thing[31];
int Aarr[33000], Barr[33000]; // 2^15
void left_arr(int i, int sum){
if(sum > C){
return;
}
if(i == N/2){
Aarr[asize++] = sum;
return;
}
left_arr(i+1, sum + thing[i]); // 넣는 경우
left_arr(i+1, sum); // 넣지 않는 경우
}
void right_arr(int i, int sum){
if(sum > C){
return;
}
if(i == N){
Barr[bsize++] = sum;
return;
}
right_arr(i+1, sum + thing[i]); // 넣는 경우
right_arr(i+1, sum); // 넣지 않는 경우
}
void binarysearch(int start, int end, long long value){
if(start > end) return;
int mid = (start+end)/2;
if(Barr[mid] + value <= C){
idx = mid;
binarysearch(mid+1, end, value);
}
else binarysearch(start, mid-1, value);
}
int main(){
scanf("%d %d", &N, &C);
for(int i = 0; i<N; i++){
scanf("%d", &thing[i]);
}
left_arr(0, 0);
right_arr(N/2,0);
sort(Barr, Barr+bsize); // Barr를 오름차순으로 정렬
int ans = 0;
for(int i = 0; i<asize; i++){
binarysearch(0, bsize-1, Aarr[i]);
ans += idx+1;
}
printf("%d\n", ans);
}
