b1450. 냅색문제

 

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

 

 

 

📌 자바(Java)로 푸는 부분 수열의 합 문제 - 백준 1450 🎒

 

🔎 문제 개요

 

백준 1450번 - 냅색 문제는

최대 N = 30개의 물건이 주어질 때,

각 물건의 무게를 더해 총합이 C 이하인 경우의 수를 구하는 문제입니다.

 

• 1 ≤ N ≤ 30, 1 ≤ C ≤ 1e9
• 무작정 모든 조합을 돌리면 2³⁰ ≈ 10억 개, 시간 초과 발생❌
• ➡ 그래서 “Meet in the Middle(중간에서 만나기)” 전략을 사용합니다.

 

---

🛠 알고리즘 접근 방식: Meet in the Middle

 

 

✏️ 핵심 전략

 

1. 배열을 반으로 나누고 각각 가능한 부분합의 조합을 모두 구함
2. 한 쪽 배열의 조합을 기준으로, 나머지에서 더해도 C 이하가 되는 조합 개수를 이진 탐색으로 세기

 

결국 O(2^(N/2) * log(2^(N/2)) ≈ 2^15 * 15 ≈ 수십만 연산으로 해결 가능

 

---

🔹 Java 코드 설명

sumCombination(0, N/2, left, 0);
sumCombination(N/2, N, right, 0);

✔ 입력 배열을 반으로 나누어, 각각 모든 조합의 합을 리스트에 저장

✔ 예: [1,2,3] → 가능한 부분합: 0, 1, 2, 3, 1+2, 2+3, ...

 

private static void sumCombination(int start, int end, ArrayList<Long> list, long sum) {
    if(end == start){
        if(sum <= C) list.add(sum);
        return;
    }
    sumCombination(start + 1, end, list, sum);
    sumCombination(start + 1, end, list, sum + weights[start]);
}

✔ 부분 조합을 DFS 방식으로 탐색

✔ 각 분할된 구간에 대해 가능한 모든 부분합을 기록

 

Collections.sort(right);

✔ 오른쪽 리스트는 이진 탐색을 위해 정렬

 

for (long sumL : left) {
    if (sumL > C) continue;
    long remain = C - sumL;
    int idx = upperBound(right, remain);
    count += idx;
}

✔ 왼쪽 조합을 기준으로,

✔ 오른쪽에서 sumL + sumR ≤ C를 만족하는 sumR 개수를 upperBound()로 구함

 

 

📌 upperBound 함수

private static int upperBound(ArrayList<Long> list, long remain) {
    int leftIdx = 0, rightIdx = list.size();
    while(leftIdx < rightIdx){
        int mid = (leftIdx + rightIdx) / 2;
        if(list.get(mid) <= remain){
            leftIdx = mid + 1;
        } else rightIdx = mid;
    }
    return leftIdx;
}

✔ list[i] ≤ remain을 만족하는 최대 인덱스를 찾는 upper bound

✔ leftIdx가 곧 가능한 수의 개수가 됨

 

---

🏆 정리

 

 

✅ 핵심 포인트

 

• N이 작지만, 부분집합이 너무 많을 때는 → Meet in the Middle 전략
• 전체 조합을 나눠서 각각 부분합을 저장하고, 이진 탐색으로 카운트
• upperBound를 활용한 빠른 범위 내 조합 개수 계산