냅색 문제
문제
세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다.
N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 C가 주어진다.
N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다.
둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다.
출력
첫째 줄에 가방에 넣는 방법의 수를 출력한다.
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
예제 입력 1
2 1
1 1
예제 출력 1
3
예제 입력 2
1 1
1
예제 출력 2
2
예제 입력 3
1 2
1
예제 출력 3
2
예제 입력 4
2 1
2 2
예제 출력 4
1
예제 입력 5
2 2
1 1
예제 출력 5
4
예제 입력 6
30 30
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
예제 출력 6
1073741824
풀이
합이 0인 네 정수(7453, G2) 이 문제랑 아이디어가 비슷하다고 생각된다.
가운데서 만나기? 라는 이름이 붙은 알고리즘인데 절반으로 분할해서 계산하는 느낌이다.
이것도 숫자가 30개니까 브포로 다 하려면 2^30이 걸리므로 반으로 잘라 2^15*2로 계산한다.
투 포인터로 하는 것보다 이분 탐색 코드가 더 직관적인 것 같다.
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
71
72
73
74
75
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
vector<long long> v;
int check[45] = {0};
vector<long long>sum1;
vector<long long>sum2;
long long total=0;
int n, m;
void back(int k, int x){ //절반 앞
sum1.push_back(total);
for(int i=x;i<(n/2);i++){
if(check[i]==0){
total += v[i];
check[i]=1;
back(k+1, i);
check[i]=0;
total-=v[i];
}
}
}
void back2(int k, int x){ //절반 뒤
sum2.push_back(total);
for(int i=x;i<n;i++){
if(check[i]==0){
total += v[i];
check[i]=1;
back2(k+1, i);
check[i]=0;
total-=v[i];
}
}
}
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long a, b, c, d;
long long ans;
long long cnt = 0;
cin >> n >> ans;
for(int i=0;i<n;i++){
cin >> m;
v.push_back(m);
}
back(0,0);
total=0;
back2(0,n/2);
sort(sum1.begin(), sum1.end());
sort(sum2.begin(), sum2.end());
for(int i=0;i<sum1.size();i++){
int l = 0;
int r = sum2.size();
int mid=0;;
while(l+1<r){
mid = (l+r)/2;
if(ans-sum1[i]<0){
r=0;
break;
}
if(sum2[mid] <= ans-sum1[i]) l=mid;
else r=mid;
}
cnt += r;
}
cout << cnt;
return 0;
}