[백준] 1450 냅색문제

---

DP에서 유명한 냅색 문제이지만, 이 문제는 최대 경우의 수가 2^30이기 때문에 DP를 통해서 해결할 수는 없다.

 

이전에 해결했던 부분수열의 합2와 같이 배열을 반으로 나누어 시간복잡도를 줄여야 한다. 주어진 하나의 배열을 Left, Right 2개의 배열로 나눈 후 부분수열을 구하는 알고리즘을 활용하여 원소들의 합을 구한다.

 

두 부분수열의 합 배열 중 하나만 선택하여 정렬하고, 나머지 하나의 배열의 원소를 주어진 C에서 빼 정렬한 배열을 Upper Bound 알고리즘을 통하여 문제를 해결한다.

 

Upper Bound 알고리즘은 주어진 값 보다 큰 원소가 나타나는 첫번째 위치를 반환하는 알고리즘이다. 반면 Lower Bound 알고리즘은 주어진 값 보다 크거나 같은 값이 나타나는 첫 번째 위치를 반환하는 알고리즘이다.

 

Python

	from sys import stdin
	readline = stdin.readline
	N, C = map(int, readline().split())
	arr = list(map(int, readline().split()))
	def solve():
	ans = 0
	mid = len(arr) // 2
	left, right = arr[:mid], arr[mid:]
	left_sums, right_sums = [0], [0]
	get_perm_sums(left, 0, 0, left_sums)
	get_perm_sums(right, 0, 0, right_sums)
	right_sums.sort()
	for val in left_sums:
	# upper_bound > C-val 보다 큰 원소의 첫번째 위치 반환
	cnt = upper_bound(right_sums, C-val)
	ans += cnt
	print(ans)
	def upper_bound(array, flag):
	left, right = 0, len(array) - 1
	while left < right:
	mid = (left + right) // 2
	if array[mid] < flag:
	left = mid + 1
	else:
	right = mid
	# array의 마지막 원소가 flag와 같은 경우
	if array[right] <= flag:
	right += 1
	return right
	def get_perm_sums(array, start, cur, res):
	for i in range(start, len(array)):
	if cur + array[i] <= C:
	res.append(cur + array[i])
	get_perm_sums(array, i+1, cur + array[i], res)
	solve()

view raw BOJ1450.py hosted with ❤ by GitHub

Java

	import java.util.*;
	import java.io.*;
	public class BOJ1450 {
	static int N, C;
	static int[] arr;
	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());
	arr = new int[N];
	st = new StringTokenizer(br.readLine());
	for(int i=0;i<N;i++){
	arr[i] = Integer.parseInt(st.nextToken());
	}
	solve();
	}
	public static void solve(){
	long ans = 0;
	int[] left = split_arr(0, arr.length/2);
	int[] right = split_arr(arr.length/2, arr.length);
	ArrayList<Integer> left_sums = new ArrayList<>();
	ArrayList<Integer> right_sums = new ArrayList<>();
	get_perm_sums(left, 0, 0, left_sums);
	get_perm_sums(right, 0, 0, right_sums);
	left_sums.add(0);
	right_sums.add(0);
	Collections.sort(right_sums);
	for(int val : left_sums){
	int cnt = upper_bound(right_sums, C-val);
	ans += cnt;
	}
	System.out.println(ans);
	}
	public static int upper_bound(ArrayList<Integer> array, int val){
	int left = 0, right = array.size() - 1;
	while(left < right){
	int mid = (left + right) / 2;
	if(array.get(mid) <= val){
	left = mid + 1;
	} else {
	right = mid;
	}
	}
	if(array.get(right) <= val){
	right++;
	}
	return right;
	}
	public static void get_perm_sums(int[] array, int start, int cur, ArrayList<Integer> res){
	for(int i=start;i<array.length;i++){
	if(cur + array[i] <= C){
	res.add(cur + array[i]);
	get_perm_sums(array, i+1, cur + array[i], res);
	}
	}
	}
	public static int[] split_arr(int start, int end){
	int[] res = new int[end-start];
	int idx = 0;
	for(int i=start;i<end;i++){
	res[idx++] = arr[i];
	}
	return res;
	}
	}

view raw BOJ1450.java hosted with ❤ by GitHub