[백준] 1450: 냅색문제

문제 출처 : https://www.acmicpc.net/problem/1450

소요 시간 : 풀이(1h)

---

문제

---

시도

 

투 포인터의 최종 문제로 난이도가 상당했다.

 

일단 일반적인 접근법인 start, end의 두 기준으로 투 포인터를 구현했는데, 풀다보니 해당 문제는 경우의 수까지 고려해야 하는 문제라는 걸 알게 되었고, 결국 다른 사람의 풀이를 참고했다.

 

---

풀이

 

해당 문제의 접근법은 다음과 같다.

 

1. N을 반으로 나누어 start ~ N/2, N/2 ~ end 범위에서 각각 완전탐색을 하여 만들 수 있는(C 이하) 모든 무게를 찾아 각각 배열(aSum, bSum)에 담는다.
2. aSum, bSum 중 하나를 기준으로 이진탐색을 수행해야 하기에 기준이 아닌 다른 배열을 오름차순으로 정렬한다.
3. aSum 각각의 모든 무게에 대해 bSum의 무게 중 하나를 합쳐서 C보다 작은 bSum에서의 인덱스를 찾는다.
   • 찾더라도 start > end일 때까지 이진탐색을 수행한다.
   • 이는 aSum의 무게 + bSum의 무게가 C 이하지만 최대로 되는 인덱스를 찾으면 bSum의 0번째부터 찾은 인덱스까지는 모두 aSum의 무게와 더했을 때 C 이하이기 때문이다.

 

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

class Main {

    static int n, c, index;
    static int[] arr;
    static ArrayList<Integer> aSum, bSum;

    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());    // 1 ~ 30
        c = Integer.parseInt(st.nextToken());    // 0 ~ 10^9
        arr = new int[n + 1];

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

        aSum = new ArrayList<>();
        bSum = new ArrayList<>();

        aBruteForce(0, 0);
        bBruteForce(n/2, 0);
        Collections.sort(bSum);

        int ans = 0;
        for (int i = 0; i < aSum.size(); i++) {
            index = -1;
            binarySearch(0, bSum.size() - 1, aSum.get(i));
            ans += index + 1;
        }

        System.out.println(ans);
    }

    static void aBruteForce(int i, int sum) {
        if (sum > c) return;

        if (i == n / 2) {
            aSum.add(sum);
            return;
        }

        aBruteForce(i + 1, sum + arr[i]);
        aBruteForce(i + 1, sum);
    }

    static void bBruteForce(int i, int sum) {
        if (sum > c) return;

        if (i == n) {
            bSum.add(sum);
            return;
        }

        bBruteForce(i + 1, sum + arr[i]);
        bBruteForce(i + 1, sum);
    }

    static void binarySearch(int start, int end, int val) {
        if (start > end) return;

        int mid = (start + end) / 2;

        if (bSum.get(mid) + val <= c) {
            index = mid;
            binarySearch(mid + 1, end, val);
        } else {
            binarySearch(start, mid - 1, val);
        }
    }
}

 

참고 출처 : https://gre-eny.tistory.com/141