[JAVA] 백준 1450 냅색문제

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

1450번: 냅색문제

 

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

- N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램

 

 

문제 풀이 

 

meet in the middle 알고리즘 

밋 인더 미들 (Meet in the middle, 중간에서 만나기) 알고리즘 (백준 BOJ 1450) (tistory.com)

밋 인더 미들 (Meet in the middle, 중간에서 만나기) 알고리즘 (백준 BOJ 1450)

 

[백준] 투 포인터 - 1450번: 냅색 문제 (Java) (tistory.com)

[백준] 투 포인터 - 1450번: 냅색 문제 (Java)

 

냅색 문제 (1450, 골드 1) - 자바 Java 백준 문제 풀이 (youtube.com)

 

 

- 한 개의 그룹으로 완전 탐색을 하지 못하는 경우 두 개의 그룹으로 나누어 탐색하여 그 결과를 확인하여 시간을 줄이는 알고리즘

- N이 그렇게 크지 않지만 완전 탐색을 진행하기엔 무리가 있다고 판단할 때 주로 사용하는 알고리즘  

 

- N개의 물건 각각의 무게를 가지고 있고 최대 C만큼의 무게를 넣을 수 있는 가방에 물건들을 넣는 방법의 수를 구하는 문제 

- 물건의 수가 최대 30개이고 각 물건은 가방에 넣는다와 안 넣는다의 두 가지 선택지가 있으므로 모든 경우의 수를 따지면 최대 2^30의 연산이 필요하다.

 

- meet in the middle 알고리즘을 사용하여 풀이를 해보면, 0 ~ N/2번째 원소까지를 그룹 A로 N/2+1 ~N번째 원소까지를 그룹 B로 만든 다음, 그룹 A의 각 원소에 대해 합이 C 이하의 크기를 가지는 그룹 B의 원소 수를 합하여 답을 구하면 된다. 

- 그룹 A와 그룹 B의 원소를 구하는 데 걸리는 시간은 각각 O(2^(N/2))이므로 최대 2^15 = 65,536 정도의 연산이 필요하므로 여유롭게 통과 가능하다 .

 

- 또한 마지막에 경우의 수를 counting해주는 과정에서는 2^(N/2)에다가 B의 정렬된 원소를 이분탐색하므로 log(2^(N/2)) = N 즉, 곱해주면 O(N*2^(N/2)) 정도로 생각할 수 있다 .

 

 

 

 

- weight1과 weight2가 각각의 배낭이라고 생각하고 각각의 경우의 수 계산 

-  두 물건을 모두 다 담는 경우, 앞에 물건만 담는 경우, 뒤에 물건만 담는 경우, 둘다 담지 않는 경우 

 

 

 

- sum2 배열 정렬해줌 

-> why? sum1에 있는 값과 sum2에 있는 값을 조합을 해서 c라는 값 이하가 되는 수가 몇개가 있는지 궁금

 -> 정렬을 함으로써 이진 탐색이 가능해짐

- sum1의 하나 인덱스를 잡고  얘를 기준으로 해서 sum2의 각각의 인덱스를 더해봐서 그 각각의 더한 값이 C보다 작거나 같은지를 확인하고 싶음 

 

시간 복잡도 

 

 

 

정답 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
	static int N,C;
    
    //이진 탐색
    static int binarySearch(ArrayList<Integer> sum, int target)
    {
        int left =0,right = sum.size()-1, mid,answer = -1;
        
        while(left<=right)
        {
            mid = (left+right)/2;
            if(sum.get(mid)<=target)
            {
                answer = mid;
                left = mid +1; 
            }
            else
            {
                right = mid -1;
            }
        }
        return answer;
    }
    
    //dfs
    static void dfs(int idx, int sum, ArrayList<Integer> weight, ArrayList<Integer> answer)
    {
        //3. 탈출 조건
        if(sum > C) return;
        
        if(idx == weight.size())
        {
            answer.add(sum);
            return;
        }
        
        //1. 물건을 넣는 경우
        dfs(idx+1, sum+weight.get(idx), weight, answer);
        
        //2. 물건을 넣지 않는 경우 
        dfs(idx+1, sum, weight, answer);
    }
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken()); 
        C = Integer.parseInt(st.nextToken());
        ArrayList<Integer> weight1 = new ArrayList<>();
        ArrayList<Integer> weight2 = new ArrayList<>();
        
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++)
        {
            if(i<N/2)
            {
                weight1.add(Integer.parseInt(st.nextToken()));
            }
            else
            {
                weight2.add(Integer.parseInt(st.nextToken()));
            }
        }
        
        //1. dfs로 sum1 , sum2 만들기 
        ArrayList<Integer>sum1 = new ArrayList<>();
        ArrayList<Integer>sum2 = new ArrayList<>();
        
        dfs(0,0,weight1,sum1); 
        dfs(0,0,weight2,sum2); 
        
        //2. sort 및 binary search
        Collections.sort(sum2);
        int answer = 0;
        for(int i=0; i<sum1.size(); i++)
        {
            //C라는 최댓값에서 현재의 값을 빼면 sum2에서 찾아야 될 값이 담김
            int searchValue = C - sum1.get(i);
            answer +=binarySearch(sum2, searchValue)+1;
        }
        
        bw.write(String.valueOf(answer));
        
        bw.flush();
        bw.close();
        
    }
}