[SWEA] 2115 벌꿀채취 (조합, 부분집합/Java)

[SWEA] 2115 벌꿀채취

📌 풀이 과정

두 명의 일꾼이 최대 수익을 얻을 수 있도록 꿀을 채취하는 구간을 선택해야 한다.

각 일꾼이 채취할 수 있는 벌통의 수와 꿀의 최대 양이 정해져있기 때문에, 이 조건을 잘 생각해야 한다.

각 구간에서 선택할 수 있는 벌통의 부분 집합 중에서 최대 수익을 미리 구해두면
이후 두 일꾼이 벌통을 선택할 때 그 값을 재사용할 수 있기 때문에 최대 수익을 먼저 계산하도록 하자!!!

아래 코드에서 profit 배열에 각 구간의 최대 수익을 미리 계산해두면

두 일꾼이 벌통 구간을 선택할 때 해당 구간의 최대 수익만 참조하면 된다.

1. 최대 수익 계산

각 구간에서 얻을 수 있는 최대 수익을 계산해야 한다.

일꾼이 꿀을 채취할 수 있는 모든 가능한 구간에 대해 최대 수익을 구한다.

2. 두 일꾼의 조합 계산

두 일꾼의 조합을 선택해, 각 조합의 최대 수익을 계산한다.

첫번째 일꾼이 채취한 후, 두번째 일꾼이 채취할 수 있는 구간을 계산하여 최종 최대 수익값을 갱신한다.

 

✨ 제출 코드

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

public class Solution {

    static int N, M, C, ans;
    static int[][] honey;
    static int[][] profit;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {

            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken()); // N : 벌통의 크기
            M = Integer.parseInt(st.nextToken()); // M : 채취할 수 있는 벌통의 수
            C = Integer.parseInt(st.nextToken()); // C : 두 일꾼이 채취할 수 있는 꿀의 최대 양
            profit = new int[N][N]; // 꿀을 담을 용기
            honey = new int[N][N];

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

            ans = 0;
            process();

            System.out.println("#" + tc + " " + ans);
        }

    }

    private static void process() {

        // 꿀을 채취할 수 있는 구간에서 얻을 수 있는 최대 수익
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= N - M; j++) {
                // 여기서 얻을 수 있는 최대 수익(부분집합)
                profitSubset(i, j, 0, 0, 0);
            }
        }

        // 일꾼 A가 채취할 구간
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= N - M; j++) {
                combination(i, j + M, 1, profit[i][j]); // 일꾼 B: j+M 꿀통부터 선택 가능
            }
        }

    }

    private static void combination(int x, int y, int cnt, int sum) {

        if(cnt == 2) {
            ans = Math.max(ans, sum);
            return;
        }

        // 일꾼 B가 채취할 구간
        for (int i = x; i < N; i++) {
            for (int j = y; j <= N - M; j++) {
                combination(i, j, cnt + 1, sum + profit[i][j]);
            }
            y = 0; // 일꾼 B: 다음 행에선 y=0 부터 선택가능
        }
    }


    private static void profitSubset(int i, int j, int cnt, int sum, int totalSum) {

        if(sum > C) return;
        if(cnt == M) {
            // 해당 구간에서 최대 수익 갱신
            profit[i][j - M] = Math.max(profit[i][j - M], totalSum);
            return;
        }
        // 이 꿀을 채취해보자
        profitSubset(i, j + 1, cnt + 1, sum + honey[i][j], totalSum + honey[i][j] * honey[i][j]);
        // 이 꿀은 채취 안하고
        profitSubset(i, j + 1, cnt + 1, sum, totalSum);

    }

}

 

처음엔 2차원 배열을 1차원 배열 형태로 전환해서

일꾼들이 M만큼 벌통을 조합으로 선택하게 하고 최대 수익을 계산하는.. 그런 로직을 떠올렸는데

쉽게 풀리지 않았다..... 이 문제 정답률 왜 67퍼냐........😭