[SWEA] 1952번 - 벌꿀채취 풀이 및 코드 분석 (Java)

문제 링크

---

1. 문제 분석

📌 문제 개요

• N x N 크기의 벌통 배열이 있다.
• 두 명의 일꾼이 가로로 M개의 벌통을 선택하여 꿀을 채취해야 한다.
• 두 일꾼의 선택한 벌통이 겹치면 안 된다.
• 각 일꾼은 C 이하의 꿀만 채취 가능하며, 수익은 꿀의 양의 제곱합이다.
• 최대 수익을 얻는 경우를 찾아야 한다.

🎯 요구사항

1. 두 일꾼이 서로 겹치지 않는 위치에서 벌통을 선택해야 한다.
2. 각 일꾼이 채취할 꿀의 양이 C 이하인 경우의 수익을 계산해야 한다.
3. 두 일꾼이 얻을 수 있는 최대 수익을 구해야 한다.
4. 완전 탐색을 이용하여 가능한 모든 경우를 조사해야 한다.

---

2. 해결 방법

🔹 핵심 개념

• 모든 가능한 조합을 완전 탐색(Brute Force)
• 각 일꾼의 최대 수익을 구하는 방법: 부분집합 탐색(백트래킹)

🔑 해결 절차

1. 모든 가능한 두 일꾼의 위치 조합을 탐색
   • first 일꾼이 (r, c) ~ (r, c+M-1)을 선택했을 때
   • second 일꾼이 first와 겹치지 않도록 다른 위치를 선택
2. 각 일꾼이 선택한 벌통에서 최대로 얻을 수 있는 수익을 계산
   • 백트래킹을 활용한 부분집합 탐색
   • C 이하의 꿀을 채취하는 경우의 제곱합이 가장 큰 값을 찾기
3. 두 일꾼의 최대 수익을 합산하여 최댓값을 갱신
   • max(total, ans1 + ans2)

---

3. 코드 구현

import java.io.*;
import java.util.*;

public class Solution {
    static int N, M, C, maxProfit;
    static int[][] honey;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            sb.append("#").append(t).append(" ");
            maxProfit = 0;

            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());

            honey = new int[N][N];

            for (int r = 0; r < N; r++) {
                st = new StringTokenizer(br.readLine());
                for (int c = 0; c < N; c++) {
                    honey[r][c] = Integer.parseInt(st.nextToken());
                }
            }

            findMaxProfit();
            sb.append(maxProfit).append("\n");
        }
        System.out.println(sb);
    }

    // 두 일꾼이 선택할 수 있는 최대 수익 찾기
    private static void findMaxProfit() {
        for (int r1 = 0; r1 < N; r1++) {
            for (int c1 = 0; c1 <= N - M; c1++) {
                int profit1 = getMaxHoneyProfit(r1, c1);

                for (int r2 = r1; r2 < N; r2++) {
                    for (int c2 = 0; c2 <= N - M; c2++) {
                        if (r1 == r2 && !(c2 >= c1 + M)) continue; // 겹치는 경우 제외

                        int profit2 = getMaxHoneyProfit(r2, c2);
                        maxProfit = Math.max(maxProfit, profit1 + profit2);
                    }
                }
            }
        }
    }

    // 백트래킹을 이용한 최적의 수익 찾기
    private static int getMaxHoneyProfit(int row, int col) {
        int[] selected = new int[M];
        for (int i = 0; i < M; i++) {
            selected[i] = honey[row][col + i];
        }
        return getMaxSubsetProfit(selected, 0, 0, 0);
    }

    // 부분집합 탐색을 통한 최대 수익 계산
    private static int getMaxSubsetProfit(int[] arr, int idx, int sum, int profit) {
        if (sum > C) return 0; // 채취량 초과 시 무효

        if (idx == arr.length) return profit; // 모든 벌통을 확인했을 때의 최댓값 반환

        // 현재 벌통을 선택하는 경우와 선택하지 않는 경우 비교
        return Math.max(
            getMaxSubsetProfit(arr, idx + 1, sum + arr[idx], profit + arr[idx] * arr[idx]), 
            getMaxSubsetProfit(arr, idx + 1, sum, profit)
        );
    }
}

---

4. 코드 분석

🔹 주요 알고리즘

1. 두 일꾼이 선택할 수 있는 모든 경우의 조합을 탐색
   • findMaxProfit()에서 모든 가능한 위치에서 일꾼 1을 선택
   • 일꾼 1과 겹치지 않는 위치에서 일꾼 2를 선택
2. 각 일꾼의 최대 수익을 계산
   • getMaxHoneyProfit()을 통해 M개의 벌통에서 최대 수익 찾기
   • getMaxSubsetProfit()을 이용하여 부분집합 탐색(백트래킹)
3. 부분집합 탐색을 활용한 최댓값 찾기
   • C 이하의 꿀을 채취하는 경우의 제곱합이 가장 큰 값을 찾음

🔹 시간 복잡도 분석

• 일꾼 1의 위치 선택: O(N^2)
• 일꾼 2의 위치 선택: O(N^2)
• 최대 수익 찾기 (부분집합 탐색): O(2^M) (최대 O(32))
• 총 시간 복잡도: O(N^4 * 2^M) ≈ O(10^4 * 32) = O(3.2 * 10^5)

✔ N ≤ 10, M ≤ 5이므로 충분히 빠르게 동작 가능!

---

5. 개선할 점 및 대체 방법

✅ 개선할 점

1. 메모이제이션을 추가하여 중복 계산 줄이기
   • getMaxSubsetProfit() 결과를 캐싱하면 연산 속도 향상 가능
2. 비트마스킹을 활용한 부분집합 탐색
   • 2^M의 부분집합 탐색을 비트마스킹(1 << M)으로 최적화 가능
3. DFS + DP 활용 가능
   • dp[r][c]를 사용하여 최대 수익을 저장하면 중복 계산을 줄일 수 있음

🔄 대체 방법

1. Dynamic Programming(DP) 활용
   • 부분집합 탐색을 DP로 변경하면 속도를 더 빠르게 최적화 가능
2. Bitmask DP 적용 가능
   • M ≤ 5이므로 32개의 부분집합을 비트마스크로 처리 가능