[DP] 가방에 물건 담기

문제 설명

 

풀이

import java.util.*;

public class BagProblem {

    static int[] weights; // 물건들의 무게
    static int n, k, t; // n: 물건 개수, k: 최소 선택 개수, t: 최대 무게
    static int count = 0; // 경우의 수 카운트

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 첫째 줄에 n, k, t 입력
        n = scanner.nextInt();
        k = scanner.nextInt();
        t = scanner.nextInt();

        // 둘째 줄에 물건들의 무게 배열 입력
        weights = new int[n];
        for (int i = 0; i < n; i++) {
            weights[i] = scanner.nextInt();
        }

        // 재귀 호출 시작
        findCombinations(0, 0, 0);

        // 경우의 수 출력
        System.out.println(count);
        scanner.close();
    }

    // 재귀 함수
    static void findCombinations(int cur, int cnt, int sum) {
        // 조건 확인: 최소 k개 선택 및 무게 합이 t 이하일 때
        if (cnt >= k && sum <= t) {
            count++; // 조건을 만족할 때 경우의 수 증가
        }

        // 물건을 선택하는 경우와 선택하지 않는 경우를 재귀 호출
        for (int i = cur; i < n; i++) {
            findCombinations(i + 1, cnt + 1, sum + weights[i]); // 선택하는 경우
        }
    }
}

이 방식은 부분집합 탐색을 기반으로 하여 현재 위치에서 물건을 선택하는 경우를 처리하는 방식입니다. 

for문이 다음 인덱스로 이동하면서 선택하지 않는 경우를 자연스럽게 처리해 주기 때문에

재귀 함수 호출에서 선택하지 않는 경우는 따로 처리하지 않아도 됩니다.

 

---

핵심 개념

재귀적으로 물건을 선택하거나 선택하지 않으면서 모든 경우를 탐색하는 것이 목표입니다.

1. 재귀 호출: findCombinations(i + 1, cnt + 1, sum + weights[i])
   • 여기서 i는 현재 물건의 인덱스를 의미하며, i+1은 다음 물건으로 이동하는 것입니다.
     (재귀 호출을 진행할 때 마다 i+1을 넘김으로써, 이미 선택한 물건은 다시 선택하지 않도록 함.)
   • cnt + 1은 현재 물건을 선택했으므로 선택한 물건 개수를 1 증가시키는 것입니다.
   • sum + weights[i]는 현재 선택한 물건의 무게를 합산한 값을 재귀 호출에 전달하는 것입니다.
2. 백트래킹 구조: 현재 인덱스에서 물건을 선택할지 말지를 탐색하고, 그 이후의 물건들에 대해 다시 같은 선택을 반복합니다.

---

 

예시

예를 들어, 배열이 [2, 5, 3, 8, 1]이고, 최소 k = 3개의 물건을 선택하면서 그 무게의 합이 t = 11 이하가 되어야 하는 경우.

 

초기상태

• n = 5, k = 3, t = 11
• 물건 배열 weights = [2, 5, 3, 8, 1]
• 처음 함수 호출: findCombinations(0, 0, 0)

1. 첫 번째 호출 findCombinations(0, 0, 0)

• cur = 0, cnt = 0, sum = 0인 상태에서 for문이 시작됩니다.
• i = 0부터 시작하므로 첫 번째 물건 weights[0] = 2을 선택.
  • 새로운 호출: findCombinations(1, 1, 2) (다음 물건으로 넘어가고, 선택 개수와 무게를 갱신)

2. 두 번째 호출 findCombinations(1, 1, 2)

• 현재까지 선택한 물건 무게 합이 2이고, 물건 하나를 선택했습니다.
• 이제 for문에서 i = 1이므로 두 번째 물건 weights[1] = 5를 선택.
  • 새로운 호출: findCombinations(2, 2, 7) (두 번째 물건을 선택하고, 선택 개수와 무게를 갱신)

3. 세 번째 호출 findCombinations(2, 2, 7)

• 현재까지 선택한 물건 무게 합이 7이고, 물건 두 개를 선택했습니다.
• for문에서 i = 2이므로 세 번째 물건 weights[2] = 3을 선택.
  • 새로운 호출: findCombinations(3, 3, 10) (세 번째 물건을 선택, 무게 합은 10)

4. 네 번째 호출 findCombinations(3, 3, 10)

• 현재까지 선택한 무게 합이 10이고, 물건 세 개를 선택했습니다. 조건인 cnt >= k와 sum <= t를 만족합니다.
  • count++이 호출됩니다.
• 이제 for문에서 i = 3이므로 네 번째 물건 weights[3] = 8을 선택하려 하지만, 무게 합이 18이 되어 t = 11을 초과합니다. 재귀 호출하지 않고 넘어갑니다.
• i = 4로 다섯 번째 물건 weights[4] = 1을 선택.
  • 새로운 호출: findCombinations(5, 4, 11) (네 번째 물건 선택, 무게 합 11)
  • 조건을 만족하므로 count++이 호출됩니다.

5. 세 번째 호출로 돌아와서 (findCombinations(2, 2, 7))

• 이제 i = 3으로 네 번째 물건 weights[3] = 8을 선택하려 하지만, 무게 합이 15가 되어 t를 초과. 재귀 호출하지 않고 넘어갑니다.
• i = 4로 다섯 번째 물건 weights[4] = 1을 선택.
  • 새로운 호출: findCombinations(5, 3, 8) (세 번째 물건을 선택하지 않고 다섯 번째 물건만 선택, 무게 합 8)
  • 조건을 만족하므로 count++이 호출됩니다.

---

 

트리 구조

다음은 물건이 [2, 5]일 때의 선택 과정을 보여주는 트리입니다.

                  (0, 0, 0)  -> 초기 상태
                 /         \
        (1, 1, 2)           (1, 0, 0)   -> 첫 번째 물건을 선택하거나 선택하지 않음
         /   \                /    \
(2, 2, 7)  (2, 1, 2)    (2, 1, 5)   (2, 0, 0)   -> 두 번째 물건 선택 또는 선택하지 않음

(cur, cnt, sum)는 각각 현재 인덱스, 선택한 물건 개수, 선택한 무게 합을 의미

백트래킹(Backtracking)의 전형적인 방식이다.

 

---

20년도 쿠팡 신입 기출문제.

대표적인 DP 문제 이다.