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

#. Problem

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu&categoryId=AV5V4A46AdIDFAWu&categoryType=CODE

* The copyright in this matter is in SWEA

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

전체적인 동작은

1. 해당 구간에서 얻을 수 있는 최대 수익을 미리 계산

꿀을 채취할 수 있는 최대량이 정해져 있으므로 부분집합으로 최대 수익 계산

2. 일꾼 A가 채취할 구간을 먼저 정한 후 일꾼 B가 채취할 구간을 조합으로 정해주자.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class Solution2115 {       static int N, M, C, res, map[][], 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]; // 꿀을 담을 용기             map = new int[N][N];                          for (int i = 0; i < N; i++) {                 st = new StringTokenizer(br.readLine());                 for (int j = 0; j <N; j++) {                     map[i][j] = Integer.parseInt(st.nextToken());                 }             }                          res = 0;             process();                          System.out.println("#" + tc + " " + res);         }       }       private static void process() {                  // 꿀을 채취할 수 있는 구간에서 얻을 수 있는 최대 수익         makeProfit();         // 일꾼 A가 채취할 구간         for (int i = 0; i < N; i++) {             for (int j = 0; j <= N - M; j++) {                 combination(i, j + M, 1, profit[i][j]);             }         }              }       private static void combination(int x, int y, int cnt, int sum) {                  if(cnt == 2) {             res = Math.max(res, 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;         }     }       private static void makeProfit() {                  for (int i = 0; i < N; i++) {             for (int j = 0; j <= N - M; j++) {                 // 여기서 얻을 수 있는 최대 수익(부분집합)                 profitSubset(i, j, 0, 0, 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 + map[i][j], totalSum + map[i][j] * map[i][j]);         // 이 꿀은 채취 안하고         profitSubset(i, j + 1, cnt + 1, sum, totalSum);              }   }   Colored by Color Scripter

cs