[BOJ] 백준 1450번 냅색문제 (Java)

#1450 냅색문제

난이도 : 골드 1

유형 : 이분 탐색

1450번: 냅색문제

▸ 문제

세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다.

N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 10^9보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다.

▸ 출력

첫째 줄에 가방에 넣는 방법의 수를 출력한다.

 

문제 풀이  

물건의 최대 크기는 30개이다. 이에 나올 수 있는 모든 부분집합의 수는 2^30  = 약 10억개이다. 이를 한 번에 모두 구하여 투 포인터를 사용하면 좋겠지만, 재귀탐색 구간에서 엄청난 시간이 소요된다. 그리고 만약 시간을 오래걸려서 하나의 2^30개의 데이터를 하나의 자료구조에 넣었다고 해도 중복된 값의 구간이 많기 때문에 탐색하기도 까다롭다.

 

그래서 여기서는 일명 갈라파고스 기법을 사용해야 한다. 사실 이런 말은 없고 갈라치기를 사용하면 된다. 컴퓨터는 30개를 한 번에 쪼개는 것과  (15개, 15개) 따로 쪼개는 것과 연산 속도가 다르다. 물론 작은 값은 별 차이없겠지만 큰 값일 수록 확연하게 드러난다. 시간복잡도로 생각해보면 더 쉽다. O(2^30)과 O(2^15)+O(2^15)의 차이라고 보면 된다. 후자는 그냥 최대 O(2*2^15) = 약 6만이다. 즉, 데이터를 쪼개서 따로 계산하면 성능을 향상 시킬 수 있다는 것이다. 

• 비슷한 문제로 백준 7453번 문제가 있다.

 

 

이제 두 개의 자료구조로 C보다 작거나 같은 개수를 구하면 된다. 자료구조에는 중복된 데이터가 많기 때문에 투포인터로 일일이 탐색하기보다는 upperbound를 사용하여 left의 어떤 값 + (right (0~ upperbound.idx)) 개수를 구하는 게 더 편하다.

 

예시로, N=5, C=2, [1, 1, 1, 1, 1]의 입력 데이터가 주어졌다고 해보자. 그러면 두 개의 집합으로 나눠서 각 부분집합을 구하면 다음과 같다.

• left = [0, 1, 1, 2]
• right = [0, 1, 1, 1, 2, 2, 2]

이제 left값을 기준으로 c-left보다 작거나 같은 값에 포함되는 수를 right에서 모두 구해서 더해주면 된다.

 

 

풀이 코드 

import java.io.*;
import java.util.*;

public class Main {
	static int c;
	static int[] arr;
	static List<Integer> left, right;
	public static void main(String[] args) throws  IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int 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());
		}
		
		left = new ArrayList<>();
		right = new ArrayList<>();
		comb(left, 0, n/2, 0);
		comb(right, n/2, n, 0);
		right.sort((a,b) -> (a-b));
		
		int cnt = 0;
		int idx = 0;
		for(int i=0; i<left.size(); i++) {
			idx = upperbound(0, right.size()-1, left.get(i));
			cnt += idx+1;
		}
		System.out.println(cnt);
	}
	
	static int upperbound(int s, int e, int val) {
		while(s <= e) {
			int mid = (s+e)/2;
			if(right.get(mid) <= c-val) {
				s = mid+1;
			}else {
				e = mid-1;
			}
		}
		return e;
	}
	
	static void comb(List<Integer> list, int start, int end, int sum) {
		if(sum > c) return;
		if(start == end) {
			list.add(sum);
			return;
		}
		comb(list, start+1, end, sum);
		comb(list, start+1, end, sum + arr[start]);
	}
}