[gold1] 1450 냅색문제

https://www.acmicpc.net/problem/1450

 

냅색문제로 위장한 중간에서 만나기 문제이다.

N = 30 일때  15, 15 로 쪼개면 각각 2 ^15  의 가짓 수의 무게를 가지게 된다.

일단 앞에서부터 0~14까지의 무게의 가짓수를 리스트 halfList에 저장 후, 정렬한다.

그 후 15~29까지 무게를 구한 후        (C - 각각 무게 ) 를 이분탐색으로 halfList 에서 찾은 index + 1  만큼 정답에 더하면 된다.

0~ index 까지는  C - 무게  보다 무게가 덜 나가기 때문이다.

 

package boj1450;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.*;

public class Main {

static List<Long> halfl = new ArrayList<Long>();

static int N , C ,h;

static int [] rawl;

static int res = 0;

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());

h = N / 2;

rawl = new int[N];

st = new StringTokenizer(br.readLine());

for(int i = 0 ; i < N ; i++) {

rawl[i] = Integer.parseInt(st.nextToken());

 

}

backTrack(0, h,0,0);

Collections.sort(halfl);

backTrack(h + 1 , N - 1, 0,1);

System.out.println(res);

 

}

public static void backTrack(int s , int e ,long sum, int type) {

if(s > e) {

if(type == 0)halfl.add(sum);

else {

int l = 0 ; int r = halfl.size() - 1;

int ans = -1;

while(l <= r) {

int mid = (l + r) / 2;

if(halfl.get(mid) < C - sum + 1) {

ans = mid;

l = mid + 1;

}else {

r = mid - 1;

}

 

 

}

if(ans >= 0 ) {

res += ans + 1;

}

 

}

return;

 

}

 

for(int i= s ; i <= e ; i++) {

backTrack(i + 1, e , sum + rawl[i],type);

}

backTrack(e + 1 , e , sum, type);

 

 

}

 

}