백준 1450 자바 - 냅색문제 (BOJ 1450 JAVA)

문제 : boj1450

 

 

1. 문제 접근

  딱히 냅색과 관련없어 보이는 문제이다. N이 작아 쉽게 풀 수 있을 줄 알았다. 근데 당연하게도 모든 경우를 보면 O(2^30) 이므로 통과할 수 없다. 그렇다고 냅색처럼 DP로 풀자니 1~10^9 까지 확인해야 할 것 같으니 역시 통과할 수 없다. bit DP쪽으로도 딱히 떠오르지 않았다. 그래서 이 문제에서 적용한 방식처럼 반반을 나눠서 생각해보기로 했다.

 

1.1 최대 30개의 데이터를 대충 반반으로 15개씩 나눈다(사실 한쪽을 25개, 한쪽을 5개로 해도 상관없다.). 이걸 A와 B라 하겠다.

 

1.2 A에 대해 나올 수 있는 모든 무게 합의 경우의 수 확인하고 어딘가에 저장한다. 이 경우 최대 15번에 대해 해당 수를 포함하거나 포함하지 않거나의 2가지 경우이므로 O(2^15)가 된다.

 

1.3 B도 마찬가지로 나올 수 있는 모든 무게 합의 경우의 수를 확인하며 마찬가지로 O(2^15)이다. 그리고 'C-해당 무게 합' 보다 작은 경우의 수를 '1.2'에서 만들어둔 어딘가에서 찾는다. 이걸 B에서 나올 수 있는 모든 경우에 대해 수행하면 된다.

 

이 때, '1.1'에서 15개씩 나눈 부분은 메모리 초과와 시간 초과 여부에 따라 적절히 조절하면 된다. (예를들어 메모리 초과가 난다면 A의 모든 경우를 저장하는 메모리를 줄이기 위해 A는 10개, B는 20개 해도 된다.)

 

 

2. 구체화

  해결할 수 있어야 하는걸 정리해보자.

 

2.1 임의의 개수로 나눠진 A, B에 대해 각각 모든 경우를 탐색할 수 있어야 한다.

-> 재귀나 스택을 통해 수행하면 될 것이다.

 

2.2 A를 확인 후 어디에 저장할까? -> B에서 나왔던 경우에 대해 'C-해당 무게의 합'보다 '작은' 경우들을 알 수 있어야 하므로, 최종적으로 이분탐색으로 찾을 것이다. -> TreeMap<Integer, Integer>을 사용하고 동일한 합이 나온 경우에는 해당 합을 key로하고, value를 해당 합이 나온 횟수로 둔다.

 

2.3 TreeMap에서 특정 값보다 작은 경우를 알 수 있어야 한다. -> A에 대한 TreeMap을 만든 후, key값 오름차순으로 각 value에 대한 prefixSum을 진행한다. -> 그럼 특정 값에 대한 floorKey만 확인하면 바로 확인할 수 있다.(자바의 floorKey는 흔히 c++에서 사용하는 lowerBound라고 보면 된다.)

 

  참고로 TreeMap을 쓰지 않고 직접 이분탐색으로 찾아도 된다. 이 경우 TreeMap이 아니라 그냥 ArrayList<Integer> 같은데다가 횟수도 세지않고 늘여놓고 정렬한다. 이후 특정 값은 이분탐색으로 나온 특정 값의 upperBound의 인덱스가 결국 찾고자 하는 값이다.

  

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {
    private int n;
    private int c, answer = 0;
    private int[] arr = new int[30];
    private TreeMap<Integer, Integer> hm = new TreeMap<>();

    private void search(int idx, int sum) {
        if (sum > c) return;
        if (idx == 30 || arr[idx] == 0) {
            answer += hm.getOrDefault(hm.floorKey(c-sum), 0);
            return;
        }
        search(idx+1, sum);
        search(idx+1, sum+arr[idx]);
    }

    private void prefixSum() {
        Integer tmp = hm.firstKey();
        int sumTmp = 0;

        while (true) {
            sumTmp += hm.get(tmp);
            hm.put(tmp, sumTmp);

            tmp = hm.higherKey(tmp);
            if (tmp == null) break;
        }
    }

    private void initLeft(int idx, int sum) {
        if (sum > c) return;
        if (idx == 15 || arr[idx] == 0) {
            hm.put(sum, hm.getOrDefault(sum, 0)+1);
            return;
        }
        initLeft(idx+1, sum);
        initLeft(idx+1, sum+arr[idx]);
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(st.nextToken());

        initLeft(0, 0);
        prefixSum();
        search(15, 0);

        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}