세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다.
N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오.
첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 10의 9승보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 10의 9승보다 작거나 같은 자연수이다.
N이 30개이기 때문에 부분조합 2의 30승개의 경우의 수가 발생한다.
이 문제를 해결하기 위해 각 15개의 부분집합을 만든 후
하나의 기준 배열을 정렬하여
이분 탐색 해서 나머지 배열의 요소와 더한 값의
Higher Bound 값을 구해 그 인덱스만큼 더 해주면
2^18승 번으로 끝낼 수 있다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main {
static ArrayList<Integer> aSum;
static ArrayList<Integer> bSum;
static int array[];
static int len, N, C;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
array = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer :: parseInt).toArray();
aSum = new ArrayList<>();
bSum = new ArrayList<>();
aBrute(0, 0);
bBrute(N / 2, 0);
len = bSum.size();
Collections.sort(bSum);
long result = 0;
for(int i = 0; i < aSum.size(); i++) {
int x = aSum.get(i);
int idx = binary(x);
result += idx + 1;
}
System.out.println(result);
}
public static int binary(int n) {
int left = 0;
int right = len;
while(left < right) {
int mid = (left + right) / 2;
if(bSum.get(mid) + n <= C) {
left = mid + 1;
} else {
right = mid;
}
}
return left - 1;
}
public static void aBrute(int n, int sum) {
if(sum > C) {
return;
}
if(n == N / 2) {
aSum.add(sum);
return;
}
aBrute(n + 1 , sum + array[n]);
aBrute(n + 1, sum);
}
public static void bBrute(int n, int sum) {
if(sum > C) {
return;
}
if(n == N) {
bSum.add(sum);
return;
}
bBrute(n + 1, sum + array[n]);
bBrute(n + 1, sum);
}
}