[Boj_1450] 냅색문제

📎 문제 링크

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

 

▸ 문제

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

N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오.

 

▸ 입력

첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 10^9보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다.

 

▸ 출력

첫째 줄에 가방에 넣는 방법의 수를 출력한다.

 

📍 문제 정보

• 🥇  문제 레벨 : 골드 1
• 🔔  문제 유형 : 이분 탐색, 중간에서 만나기
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

이 문제는 물건의 수가 최대 30개이고, 각 물건은 가방에 넣거나 넣지 않는 두 가지 선택지가 있다. 
따라서 모든 경우를 완전탐색으로 계산하면 최대 2^30 ≈ 10억 가지 경우를 확인해야 한다. 
이는 1초에 1억 번 연산이 가능하다고 해도 10초 이상 걸리므로, 더 효율적인 접근이 필요하다.

 

이때 사용할 수 있는 대표적인 방법 중 하나가 중간에서 만나기(Meet in the Middle) 알고리즘이다.

 

중간에서 만나기 알고리즘이란 ? 🤔

하나의 그룹 전체를 완전탐색하기 어려울 때, 두 그룹으로 나누어 각각의 경우를 계산하고 그 결과를 조합하여 답을 구하는 방법이다.
탐색 대상을 절반으로 나누면 연산량이 크게 줄어든다.

 

🎯 그렇다면 문제에 중간에서 만나기 알고리즘을 적용해보자.

먼저, 주어진 물건을 절반으로 나누어

• 그룹 A : 0 ~ N/2 - 1
• 그룹 B : N/2 ~ N - 1

각 그룹에서 만들 수 있는 모든 부분합을 구한다.
그 후, 그룹 A의 부분합 하나를 고정하고, 그룹 B에서 C - 부분합(A) 이하가 되는 값의 개수를 찾아 더한다.

💡 가능한 경우의 수 구하기

weight1과 weight2가 각각의 그룹(배낭)이라고 생각하면, 다음과 같은 모든 경우의 수가 계산된다.

• 두 그룹의 물건을 모두 담는 경우
• 그룹 A의 물건만 담는 경우
• 그룹 B의 물건만 담는 경우
• 둘 다 담지 않는 경우

 

🧠 정렬과 이분 탐색

그룹 B의 부분합 배열(sum2)을 오름차순 정렬한다.
정렬을 하면 특정 값 이하의 원소 개수를 이분 탐색으로 빠르게 찾을 수 있다.

• sum1[i]를 기준으로 target = C - sum1[i] 계산
• sum2에서 target 이하인 원소 개수 = upperBound(sum2, target)

이 과정을 모든 sum1[i]에 대해 반복하고, 그 개수를 모두 합산하면 전체 경우의 수가 된다.

 

위 풀이의 코드를 바탕으로 전체적인 코드를 작성해 보면 아래와 같다.

 

✔ 코드

메모리 : 17288KB
시간 : 168ms

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

public class Main {
    static int n, c;
    static int[] arr;
    static ArrayList<Integer> left, right;
    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()); // 물건의 개수
        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());
        }

        left = new ArrayList<>();
        right = new ArrayList<>();
        comb(left, 0, n/2, 0);
        comb(right, n/2, n, 0);
        Collections.sort(right);

        int ans = 0;
        for (int i = 0; i < left.size(); i++) {
            int searchValue = c - left.get(i);
            // 인덱스를 반환하므로 +1
            ans += binarySearch(right, searchValue)+1;
        }

        System.out.println(ans);

        br.close();
    }

    private static int binarySearch(ArrayList<Integer> sum, int target) {
        int left = 0;
        int right = sum.size();

        while (left < right) {
            int mid = (left+right)/2;

            if (sum.get(mid) <= target) {
                left = mid+1;
            } else {
                right = mid;
            }
        }

        return left-1;
    }

    private static void comb(ArrayList<Integer> list, int start, int end, int sum) {
        if (sum > c) return; // 탈출 조건

        if (start == end) {
            list.add(sum);
            return;
        }

        // 물건을 넣는 경우
        comb(list, start+1, end, sum+arr[start]);
        // 물건을 넣지 않는 경우
        comb(list, start+1, end, sum);
    }
}

 

이분 탐색을 공부하던 중에 중간에서 만나기 알고리즘을 활용한 문제는 처음 접해서, 개념을 공부한 뒤에 풀어보았다.

코드 구조는 지금까지 작성해왔던 깊이 우선 탐색과 이분 탐색 코드와 크게 다르지 않아, 큰 어려움 없이 문제를 해결할 수 있었다.

최근 들어 비슷한 알고리즘 문제만 풀었는데 오랜만에 새로운 알고리즘 문제라 아주 재밌게 풀었다 ! 😊🌟