[백준(Baekjoon)][자바(java)] 1450 : 냅색문제 / 투 포인터

 

www.acmicpc.net/problem/1450

1450번: 냅색문제

 

문제 풀이

 

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

public class Main {
	
	public static int upper_bound( int l, int r, int t, long a[] ) {
		int m;
		while( l < r ) {
			m = ( l + r ) / 2;
			if( a[m] <= t )	l = m + 1;
			else				r = m;
		}
		return r;
	}
	
	static int idx;
	public static void com( int k, int s, int n, int m, int t[], boolean v[], int arr[], long sarr[] ) {
		if( k == m ) {
			long sum = 0;
			for( int i = 0; i < m; i++ )
				sum += arr[t[i]];
			sarr[idx++] = sum;
			return;
		}
		for( int i = s; i < n; i++ ) {
			if( !v[i] ) {
				v[i] = true;
				t[k] = i;
				com( k + 1, i + 1, n, m, t, v, arr, sarr );
				v[i] = false;
			}
		}
	}

	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() ), na = n/2, nb = n-na;
		int a[] = new int[na], b[] = new int[nb], i;
		st = new StringTokenizer( br.readLine() );
		for( i = 0; i < na; i++ )
			a[i] = Integer.parseInt( st.nextToken() );
		for( i = 0; i < nb; i++ )
			b[i] = Integer.parseInt( st.nextToken() );
		br.close();
		
		int nsa = (int)Math.pow( 2, na ) - 1, nsb = na == nb ? nsa : (int)Math.pow( 2, nb ) - 1;
		long sa[] = new long[nsa], sb[] = new long[nsb]; // sub_a, sub_b
		int t[] = new int[nsa];
		boolean v[] = new boolean[nsa];
		idx = 0;
		for( i = 1; i <= na; i++ )
			com( 0, 0, na, i, t, v, a, sa );
		t = new int[nsb];
		v = new boolean[nsb];
		idx = 0;
		for( i = 1; i <= nb; i++ )
			com( 0, 0, nb, i, t, v, b, sb );
		Arrays.sort( sa );
		Arrays.sort( sb );
		
		int r = 1;
		for( long aa : sa )
			if( aa <= c ) 
				r += 1 + upper_bound( 0, nsb, c-(int)aa, sb );
		for( long bb : sb ) 
			if( bb <= c )
				r++;
		System.out.println( r );
	}
}

 

*  투 포인터, 중간에서 만나기

-  '중간에서 만나기' 알고리즘은 배열을 반으로 쪼개 각각의 배열에서 타겟을 찾는 것이다.
   이 문제에서 입력받는 배열의 길이는 최대 30개이고, 반으로 쪼개면 각각 최대 15개이다.
   따라서 완전탐색을 수행해도 괜찮다.
-  배열을 입력받을 때 반으로 나눠 각각 a, b에 입력받고,
   조합을 구하는 함수( com() )로 각각의 배열에서 나올 수 있는 모든 합을 또 다른 배열 sa, sb에 각각 넣고 오름차순 정렬
 ( 진부분집합( 공집합을 제외한 모든 부분집합 ) 구하기 ) ( 진부분집합의 개수 = ( 2^(원소의개수) ) - 1 )
-  그런 다음 sa, sb의 값들을 각각 탐색하여 c값보다 작거나 같으면 카운트 한다.
   또한 한 쪽( ex) sa )을 탐색하며 c에서 한 요소를 뺀 값이 다른 한쪽( ex) sb )에 있는지, 있으면 그 개수를 구하여
   카운트한다. ( upper_bound -- 찾고자 하는 값( t : target )보다 큰 값이 처음으로 나오는 인덱스 리턴
                                          => 찾고자 하는 값보다 작거나 같은 수들의 개수 리턴 )

 

ex) 

5 4
2 2 1 1 4

n = 5, c = 4

na = 5 / 2 = 2
nb = 5 - 2 = 3

a[] = { 2, 2 }
b[] = { 1, 1, 4 }

nsa = 2^2 -1 = 3
nsb = 2^3 - 1 = 7

sa[] = { 2, 2, 4(2+2) }
sb[] = { 1, 1, 2(1+1), 4, 5(1+4), 5(1+4), 6(1+1+4) }

r = 1  ( 초기값. 가방에 아무 것도 안 넣은 경우 )