[백준] 1450 냅색문제 - 이진탐색

문제 링크 : https://www.acmicpc.net/problem/1450

🍊해결방법

• 냅색문제라서 dp를 활용하려 했지만 2차원 배열에서 각각 최대 10억이라 메모리초과...
• 모든 경우의 수를 따져보려 했지만 2^30이라 시간초과
• 두 그룹으로 나눠서 합이 나올 수 있는 경우의 수를 각각의 리스트에 저장
• 한개의 리스트만 정렬하여 이진탐색에 활용
• list1에 있는 모든 경우를 보면서 list2에서 이진탐색을 활용
• C이하의 무게를 만족하는 가장 큰 idx를 찾아 cnt 플러스

😀풀이

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

public class Main {

    static int[] arr;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 최대 30이라 2^30 시초, dp 냅색을 활용하려해도 10억 10억이라 안됨
        // 그룹을 반으로 나눠서 각각의 모든 경우의 수를 가지고 최대 C만큼 되는 개수 구하자
        // 이진탐색 활용

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

        int N = Integer.parseInt(st.nextToken());
        int 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());
        }

        List<Long> list1 = new ArrayList<>();
        List<Long> list2 = new ArrayList<>();

        makeSum(0,0,N/2,list1);

        makeSum(N/2, 0, N, list2);

        Collections.sort(list2);

        int cnt = 0;

        for(int i=0; i<list1.size(); i++){

            long tmp = C - list1.get(i);

            if (tmp < 0) continue;

            int s = 0;
            int e = list2.size()-1;

            int ans = -1;

            while(s <= e){

                int mid = (s+e)/2;

                if (list2.get(mid) <= tmp){
                    ans = mid;
                    s = mid + 1;
                }
                else{
                    e = mid - 1;
                }
            }

            if (ans >= 0){

                cnt += (ans+1);

            }

        }


        System.out.println(cnt);

    }

    static void makeSum(int idx, long sum, int max, List<Long> list){

        if (idx > max) return;

        if (idx == max){
            list.add(sum);
            return;
        }

        makeSum(idx+1, sum+arr[idx], max, list);

        makeSum(idx+1, sum, max, list);


    }

}