SWEA 2115. 벌꿀채취

Seoyeon Kim·2026년 2월 26일
SWEA부분집합알고리즘재귀조합

Coding

목록 보기
3/11

문제

지문

N*N개의 벌통이 정사각형 모양으로 배치되어 있다.
각 칸의 숫자는 각각의 벌통에 있는 꿀의 양을 나타내며, 꿀의 양은 서로 다를 수 있다. 아래 [Fig.1]은 N=4인 16개의 벌통을 나타낸다.

각 벌통에 있는 꿀의 양이 주어졌을 때, 다음과 같은 과정으로 벌꿀을 채취하여 최대한 많은 수익을 얻으려고 한다.
① 두 명의 일꾼이 있다. 꿀을 채취할 수 있는 벌통의 수 M이 주어질 때, 각각의 일꾼은 가로로 연속되도록 M개의 벌통을 선택하고, 선택한 벌통에서 꿀을 채취할 수 있다.
단, 두 명의 일꾼이 선택한 벌통은 서로 겹치면 안 된다.
아래 [Fig. 2]는 M=2일 때, 두 일꾼이 각각 벌통을 선택하는 다양한 예를 보여준다.

② 두 명의 일꾼은 선택한 벌통에서 꿀을 채취하여 용기에 담아야 한다.
단, 서로 다른 벌통에서 채취한 꿀이 섞이게 되면 상품가치가 떨이지게 되므로, 하나의 벌통에서 채취한 꿀은 하나의 용기에 담아야 한다.
하나의 벌통에서 꿀을 채취할 때, 일부분만 채취할 수 없고 벌통에 있는 모든 꿀을 한번에 채취해야 한다.
두 일꾼이 채취할 수 있는 꿀의 최대 양은 C 이다.

예를 들어, 아래 [Fig. 3]에서 C=10이고, 두 명의 일꾼이 선택한 벌통이 그림과 같을 때,

첫 번째 일꾼은 꿀의 양이 6과 1인 두 개의 벌통에서 모두 꿀을 채취할 수 있다.

하지만 두 번째 일꾼은 꿀의 양이 8과 5인 두 개의 벌통에서 모두 꿀을 채취할 경우,

채취한 꿀의 양이 13이 되어 C=10을 초과하기 때문에 두 개의 벌통에서 모두 꿀을 채취할 수 없다.

따라서 두 번째 일꾼은 꿀의 양이 8과 5인 벌통 중 하나를 선택하여 꿀을 채취해야 한다.

[Fig. 3]은 그 중 한 예를 보여주고 있다.

③ 채취한 꿀은 시장에서 팔리게 된다. 이때 하나의 용기에 있는 꿀의 양이 많을수록 상품가치가 높아, 각 용기에 있는 꿀의 양의 제곱만큼의 수익이 생긴다.
예를 들어 위 [Fig. 3]과 같이 꿀을 채취할 경우, 꿀의 양이 6, 1, 8인 세 개의 용기가 얻어지며 이때 수익의 합은, (66) + (11) + (8*8) = 36 + 1 + 64 = 101 이 된다.

벌통들의 크기 N과 벌통에 있는 꿀의 양에 대한 정보, 선택할 수 있는 벌통의 개수 M, 꿀을 채취할 수 있는 최대 양 C가 주어진다.

이때 두 일꾼이 꿀을 채취하여 얻을 수 있는 수익의 합이 최대가 되는 경우를 찾고, 그 때의 최대 수익을 출력하는 프로그램을 작성하라.

[예시 1]

벌통들의 크기 N=4, 선택할 수 있는 벌통의 개수 M=2, 채취할 수 있는 꿀의 최대 양 C=13 이고,

아래 [Fig. 4]와 같이 벌통에 있는 꿀의 양의 정보가 주어진 경우를 보자.

최대 수익을 얻을 수 있는 경우 중 하나로 [Fig. 4]와 같이 벌통을 선택하여 선택하여 꿀을 채취하게 되면, 총 수익이 174가 되어 최대가 된다.

따라서 이 경우 정답은 174이다.

[예시 2]

벌통의 크기 N=3, 선택할 수 있는 벌통의 개수 M=3, 채취할 수 있는 꿀의 최대 양 C=10 이고,

아래 [Fig. 5]와 같이 벌통에 있는 꿀의 양의 정보가 주어진 경우를 보자.

최대 수익을 얻을 수 있는 경우 중 하나로 [Fig. 5]와 같이 벌통을 선택하여 꿀을 채취하게 되면, 총 수익이 131이 되어 최대가 된다.

따라서 이 경우 정답은 131이다.

[제약사항]

  1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는데, C/C++/Java 모두 3초.

  2. 벌통들의 크기 N은 3 이상 10 이하의 정수이다. (3 ≤ N ≤ 10)

  3. 선택할 수 있는 벌통의 개수 M은 1 이상 5 이하의 정수이다. (1 ≤ M ≤ 5)

  4. 선택할 수 있는 벌통의 개수 M은 반드시 N 이하로만 주어진다.

  5. 꿀을 채취할 수 있는 최대 양 C는 10 이상 30 이하의 정수이다. (10 ≤ C ≤ 30)

  6. 하나의 벌통에서 채취할 수 있는 꿀의 양은 1 이상 9 이하의 정수이다.

  7. 하나의 벌통에서 일부분의 꿀만 채취할 수 없고, 벌통에 있는 모든 꿀을 한번에 채취해야 한다.

[입력]

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 벌통들의 크기 N, 선택할 수 있는 벌통의 개수 M, 꿀을 채취할 수 있는 최대 양 C가 차례로 주어진다.

그 다음 줄부터 N*N 개의 벌통에서 채취할 수 있는 꿀의 양에 대한 정보가 주어진다.

[출력]

테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다.

각 줄은 "#x"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (x는 1부터 시작하는 테스트 케이스의 번호이다)

출력해야 할 정답은 두 일꾼이 꿀을 채취하여 얻을 수 있는 최대 수익이다.

입출력 예시

[입력]
10 // 총 테스트 케이스 개수 T=10
4 2 13 // 첫 번째 테스트 케이스, N=4, M=2, C=13 (예시 1과 동일)
6 1 9 7
9 8 5 8
3 4 5 3
8 2 6 7
...

[출력]
#1 174
...

문제 정리

[목표]
N*N 크기의 벌통에서 두 명의 일꾼이 각각 가로로 연속된 M개의 벌통을 선택하여 꿀을 채취하고, 얻을 수 있는 최대 수익의 합을 구하는 것

[조건]
1. 두 일꾼(A,B)이 선택한 벌통 영역은 겹치면 안됨
1-1. 이 때, 일꾼은 각 가로로 m개 벌통을 선택하게 됨
1-2. 같은 줄에서 채취할 수 있지만, 겹치면 안됨
2. 각 일꾼은 채취한 꿀의 총합이 c를 초과할 수 없음
2-1. 이에 따라 선택한 m개의 벌통 중 일부만 골라 채취할 수 있음
2-2. 즉, (A가 채취한 꿀의 합 <= c) && (B가 채취한 꿀의 합 <= c)
3. 벌통에서 채취한 각 꿀의 양이 x일 때, 수익은 x^2의 합
3-1. 얻을 수 있는 수익 = A의 수익 + B의 수익

아이디어

변수 설정

static int n; //벌통 한 줄 크기
static int m; //각 일꾼이 선택 가능한 벌통 수
static int c; //각 일꾼이 채취할 수 있는 꿀 최대 양
static int[][] honeyMap; //벌통 
static int resultProfit; //얻을 수 있는 최대 이익. 구해야하는 값
static int tempMax; //임시 최댓값. 부분집합 문제이므로 부분집합 사이에서 최댓값 구해야함

필요 로직

  1. 일꾼 A,B 영역 구하기
    조합!!!!!
    • 두 일꾼의 영역을 겹치지 않게 하는 모든 경우의 수.
    • 이 때, 결국 우리가 구하는 값은 얻을 수 있는 최댓값이므로
      [A(0,1), B(2,3)] = [A(2,3), B(0,1)]이다.
    • 순서에 상관 없이 내부 값들의 요소가 같은 것을 조합.
  2. m개 벌통 중 가장 큰 수익을 낼 수 있는 조합 확인
    부분집합!!!!!
    • m개 벌통 중 x개를 선택하여 그 값의 합이 c가 되지 않도록(조건) 하는 것은 부분 집합
    • 선택하는 x 개수가 상관없고, 1개 이상 m개 이하이기만 하면 됨
  3. 최대 수익 계산
    • 부분집합에 대해 어떤 조합이 가장 큰 수익 내는지 계산
  4. 전체 최댓값 업데이트
    • 현재 최댓값과 비교하여 업데이트

개념 리뷰

조합

  • n개의 숫자 중 r개를 순서 없이 뽑는 경우
  • 구현에 반복문 / 재귀 등을 사용할 수 있다.
    • 반복문 : 가장 구현이 간단하다고 느끼나, 전체 원소의 개수를 무조건 알아야한다.
    • 재귀 : 원소 개수 모를 때 유용
public class Combination {
    static int n = 4;
    static int r = 2;
    static int[] arr = {1, 2, 3, 4}; // 전체 데이터
    static int[] result = new int[r]; // 뽑은 결과를 담을 배열
    public static void main(String[] args) {
        combine(0, 0);
    }
    static void combine(int start, int depth) {
        // 1. 목표 개수(r)를 다 뽑았을 때 (종료 조건)
        if (depth == r) {
            for (int val : result) {
                System.out.print(val + " ");
            }
            System.out.println();
            return;
        }
        // 2. start부터 배열의 끝까지 탐색
        for (int i = start; i < n; i++) {
            result[depth] = arr[i]; // 현재 요소 선택
            combine(i + 1, depth + 1); // 다음 요소를 뽑기 위해 재귀 호출 (i+1로 중복 방지)
        }
    }
}

부분 집합

  • 주어진 원소들 중 일부, 또는 전체를 포함하는 집합
  • 구현에 반복문 / 비트마스킹 / 재귀 등을 사용할 수 있다.
    • 반복문 : 가장 구현이 간단하다고 느끼나, 전체 원소의 개수를 무조건 알아야한다.
    • 비트마스킹 : 비트 연산 통해 구할 수 있음
    • 재귀 : 재귀 접근 통해 부분집합 구할 수 있음
      • 현재 나를 포함하는 경우, 포함하지 않는 경우로 재귀 파트 나누는 것이 포인트!
public class Subset {
    static int n = 3;
    static int[] arr = {1, 2, 3};
    static boolean[] isSelected; // 각 원소가 선택되었는지 여부를 저장
    public static void main(String[] args) {
        isSelected = new boolean[n];
        generateSubset(0);
    }
    static void generateSubset(int depth) {
        // 1. 모든 원소에 대해 결정이 끝났을 때 (종료 조건)
        if (depth == n) {
            printResult();
            return;
        }
        // 2. 현재 원소를 선택하는 경우
        isSelected[depth] = true;
        generateSubset(depth + 1);
        // 3. 현재 원소를 선택하지 않는 경우
        isSelected[depth] = false;
        generateSubset(depth + 1);
    }
    static void printResult() {
        System.out.print("{ ");
        for (int i = 0; i < n; i++) {
            if (isSelected[i]) {
                System.out.print(arr[i] + " ");
            }
        }
        System.out.println("}");
    }
}

전체 코드

import java.util.Scanner;

public class swea_2115_2 {
    static int n; //벌통 한 줄 크기
    static int m; //각 일꾼이 선택 가능한 벌통 수
    static int c; //각 일꾼이 채취할 수 있는 꿀 최대 양
    static int[][] honeyMap; //벌통 
    static int resultProfit; //얻을 수 있는 최대 이익. 구해야하는 값
    static int tempMax; //임시 최댓값. 부분집합 문제이므로 부분집합 사이에서 최댓값 구해야함

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

        int test = sc.nextInt();
        for (int t = 1; t <= test; t++) {

            n = sc.nextInt();
            m = sc.nextInt();
            c = sc.nextInt();

            honeyMap = new int[n][n];

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    honeyMap[i][j] = sc.nextInt();
                }
            }

            resultProfit = 0;

            startPoint();
            System.out.printf("#%d %d%n", t, resultProfit);

        }
    }

    //필요 로직
    //1. 일꾼 2개의 각 시작점 -> 이 때, 조합 사용
    //2. 최대 수익 계산 
    //3. 합이 c보다 작다는 조건을 만족하는 부분집합

    //1. 일꾼 2개의 각 시작점
    // -> 이 때, 조합 사용
    static void startPoint() {
        //ar 범위 : 0-(n-1)까지. 해당 문제는 가로로 이동하므로 얘는 고정시켜두고 ac가 돌아
        for (int ar = 0; ar < n; ar++) {
            //ac 범위 : 0-(n-m)까지. 시작점이기 때문에 n-m
            for (int ac = 0; ac <= n - m; ac++) {

                int aProfit = MaxProfit(ar, ac);

                //조합이기 때문에 a 이후로 따짐
                //이 때 같은 행일 가능성도 있기 대문에 br=ac부터 시작
                for (int br = ar; br < n; br++) {
                    for (int bc = 0; bc <= n - m; bc++) {
                        //다만 br,ar이 같은 행일 경우 영역 체크 필요!
                        //이 때 항상 b이 a 뒤에 온다고 생각하고..
                        //b가 a마지막 뒤로 와야하니까..
                        if (br == ar && bc < ac + m) continue;

                        int bProfit = MaxProfit(br, bc);

                        //최댓값 갱신해야하는 해당 문제에서
                        //아주 단순히 생각하는 법 :
                        //결국 최댓값은 조건을 만족하는 범위 내에서 a 최댓값 + b최댓값이 될 수밖에 없음
                        //이 조건 하 최댓값을 구하는 메서드를 만들어야 함.
                        resultProfit = Math.max(resultProfit, aProfit + bProfit);

                    }
                }
            }
        }
    }

	//2. 최대 수익 계산
    //부분집합 각 조합 중 최댓값 반환하는 메서드
    static int MaxProfit(int x, int y) {

        //초기화
        tempMax = 0;
        honeySubset(x, y, 0, 0, 0);
        return tempMax;
    }


	//3.합이 c보다 작다는 조건을 만족하는 부분 집합
    //m개의 벌꿀의 합이 c보다 작아야한다는 조건
    //이 때, 1-m개 선택해도 상관없으므로
    //부분집합
    static void honeySubset(int x, int y, int count, int sum, int profit) {
        // x , y : 현재 위치
        // count : depth와 같음 / sum : 현재 합  / profit : 계산된 이익
        // 가지치기
        // 현재 합이 c보다 크다면 보지도 말어~
        if (sum > c) return;

        // 종료 조건
        // 현재 내가 선택한 개수가 m이랑 똑같다면!
        // 쉽게 생각해, 순열에서 depth==c인 것과 같음
        if (count == m) {
            tempMax = Math.max(tempMax, profit);
            return;
        }

        //재귀
        //현재 벌통 선택
        honeySubset(x, y, count + 1, sum + honeyMap[x][y + count], profit + (honeyMap[x][y + count] * honeyMap[x][y + count]));

        //현재 벌통 선택 안 함
        honeySubset(x, y, count + 1, sum, profit);

    }


}

상세 코드

각 일꾼(A,B)의 영역 설정

	    //1. 일꾼 2개의 각 시작점
    // -> 이 때, 조합 사용
    static void startPoint() {
        //ar 범위 : 0-(n-1)까지. 해당 문제는 가로로 이동하므로 얘는 고정시켜두고 ac가 돌아
        for (int ar = 0; ar < n; ar++) {
            //ac 범위 : 0-(n-m)까지. 시작점이기 때문에 n-m
            for (int ac = 0; ac <= n - m; ac++) {

                int aProfit = MaxProfit(ar, ac);

                //조합이기 때문에 a 이후로 따짐
                //이 때 같은 행일 가능성도 있기 대문에 br=ac부터 시작
                for (int br = ar; br < n; br++) {
                    for (int bc = 0; bc <= n - m; bc++) {
                        //다만 br,ar이 같은 행일 경우 영역 체크 필요!
                        //이 때 항상 b이 a 뒤에 온다고 생각하고..
                        //b가 a마지막 뒤로 와야하니까..
                        if (br == ar && bc < ac + m) continue;

                        int bProfit = MaxProfit(br, bc);

                        //최댓값 갱신해야하는 해당 문제에서
                        //아주 단순히 생각하는 법 :
                        //결국 최댓값은 조건을 만족하는 범위 내에서 a 최댓값 + b최댓값이 될 수밖에 없음
                        //이 조건 하 최댓값을 구하는 메서드를 만들어야 함.
                        resultProfit = Math.max(resultProfit, aProfit + bProfit);

                    }
                }
            }
        }
    }

각 영역에 대한 최대 이익(각 부분집합 중 최댓값) 계산

	//2. 최대 수익 계산
    //부분집합 각 조합 중 최댓값 반환하는 메서드
    static int MaxProfit(int x, int y) {

        //초기화
        tempMax = 0;
        honeySubset(x, y, 0, 0, 0);
        return tempMax;
    }

합이 c보다 작다는 조건을 만족하는 부분집합

		//3.합이 c보다 작다는 조건을 만족하는 부분 집합
    //m개의 벌꿀의 합이 c보다 작아야한다는 조건
    //이 때, 1-m개 선택해도 상관없으므로
    //부분집합
    static void honeySubset(int x, int y, int count, int sum, int profit) {
        // x , y : 현재 위치
        // count : depth와 같음 / sum : 현재 합  / profit : 계산된 이익
        // 가지치기
        // 현재 합이 c보다 크다면 보지도 말어~
        if (sum > c) return;

        // 종료 조건
        // 현재 내가 선택한 개수가 m이랑 똑같다면!
        // 쉽게 생각해, 순열에서 depth==c인 것과 같음
        if (count == m) {
            tempMax = Math.max(tempMax, profit);
            return;
        }

        //재귀
        //현재 벌통 선택
        honeySubset(x, y, count + 1, sum + honeyMap[x][y + count], profit + (honeyMap[x][y + count] * honeyMap[x][y + count]));

        //현재 벌통 선택 안 함
        honeySubset(x, y, count + 1, sum, profit);

    }

정리

  • 음...이제 점점 제곱으로 어려워진다.
  • 조합 / 재귀 / 부분집합 등 알고리즘 기초 내용을 한 번에 리뷰해볼 수 있는 문제였음. 로직 하나하나는 어렵지 않았지만, 여러 개념을 한 번에 적용하고 구현해야했기에 복잡하게 느껴졌다.
    다음에 다시 한 번 더 이런 복합 문제 나오면 할 ? 수 ? 있을까??
  • 그리고 내가 이걸 구현하는걸 어려워했다...
    : 구현이 어려울 수록 문제 이해에 공들여서 로직을 확실히 짜고 넘어가면 그 뒤가 좀 더 쉬워지는 느낌
  • 지문에 예시가 나온다면 적극적으로 활용해서 이해할 것
  • 문제가 복잡할 수록 넘버링하자
    : 풀이 흐름을 파악하고 넘버링하면 더 쉽게 구조화될 것
  • 조합, 순열, 집합 등의 문제는 재귀를 사용하며 매우 헷갈린다.
    : 이 때, 머리로 이해하지 말고 직접 그림을 그리면 더욱 빠르게 이해할 수 있다!
  • 문제 풀이 과정은 다음을 따라가기
    1. 문제를 읽는다. 이해한다.
      1-1. 이해 못하겠으면 그림, 예시를 보고 이해한다.
      1-2. 특히 결론적으로 어떤 것을 알아내고 싶은지 목표 설정한다.
    2. 필요 변수 먼저 설정한다.
      2-1. 필요 조건, 변수가 많아지면 처음에 이걸 잘 설정하는게 중요하다.
    3. 필요한 로직을 정리한다.
      3-1. 문제를 풀기 위해 어떤 과정을 거쳐야하는지 정리한다.
    4. 각 로직에 대한 가장 적합한 구현 방식을 선택한다
      4-1. 한 로직에 대해서도 반복문 / 재귀 / 비트마스킹 등등 다양한 구현 방식이 존재한다. 조건에 따라 가장 적합한 방식을 선택하기

앞으로의 공부

  • 백트래킹 / DFS / 슬라이딩윈도우 / 브루트포스 차이와 관계

    백트래킹 : 재귀로 문제를 해결하며 해답을 찾아냄

    • 이 때 해를 얻을 때까지 모든 조합(가능성)을 시도.
    • 해를 찾는 중 막히면(해가 아니면) 돌아가서 해를 찾음 (본인을 부른 재귀로)
    • 최적화, 결정 문제 해결 가능
      - 결정 문제 : 조건 만족하는 해가 있는지 y / n로 답
      - 미로 / 부분 집합의 합 등
      .
      .
      깊이우선탐색(DFS) : 모든 경로를 차단
    • 백트래킹은 가지치기가 있는 반면 DFS는 없음
    • 백트래킹 이용 알고리즘 절차
      - 트리의 DFS 먼저 실시
      - 각 노드가 유망한지 점검
      - 유망하지 않으면 가지치기
      .
      .
      슬라이딩윈도우
    • 탐색 구간의 넓이는 고정되어있고, 탐색 위치만 계속 변경
  • 조합 코드 와 순열 코드 어떤 관계
profile
Seoyeon Kim
이전 포스트

12712. 파리퇴치3

다음 포스트

BOJ.16987 - 계란으로 계란치기

0개의 댓글