벌꿀채취 [SWEA 2115][Java]

 

[광고 누르면 오늘의 행운 상승!!]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu

SW Expert Academy

문제의 저작권은 SW Expert Academy에 있습니다.

문제는 이렇게 풀리기를 원하지 않았던 것 같은데.. 일단 풀었다.

벌들이 채취할 수 있는 블록수를 비트 마스킹을 사용하여 부분집합의 합을 구해

벌들이 채취할 수 있는 만큼의 최대치를 benefit 2차원 배열에 저장시켰다.

그리고 곂치지 않는 최대치 2개를 합친 것 중 가장 큰 수를 출력하였다.

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

public class Swea {
	public static int benefit[][];
	public static int honey[][];
	public static int N,M,C;
	public static int arr[];
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("test.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			C = sc.nextInt();
			
			honey = new int[N][N];
			benefit = new int[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					honey[i][j] = sc.nextInt();
				}
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(N - j >= M) {
						arr = new int[M];
						for (int k = 0; k < M; k++) {
							arr[k] = honey[i][j+k];
						}
						int max = 0;
						for (int k = 0; k <(1<<M); k++) {
							int sum = 0;
							int num = 0;
							for (int v = 0; v < M; v++) {
								if((k&(1<<v)) > 0) {
									num += arr[v];
									sum += arr[v] * arr[v];
								}
							}
							if(num <= C) {
								max = Math.max(sum, max);
								benefit[i][j] = max;
							}
						}
					}else {
						benefit[i][j] = honey[i][j]*honey[i][j];
					}
				}
			}

			int res = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					res = Math.max(res, otherBenefit(i, j)+benefit[i][j]);
				}
			}
			System.out.println("#" + tc + " " + res);
		}
	
	}
	public static int otherBenefit(int row, int col) {
		int ans = 0;
		
		//같은라인
		for (int i = col + M; i < N-M+1; i++) {
			ans = Math.max(ans, benefit[row][i]);
		}
		//다른 라인
		for (int i = row + 1; i < N; i++) {
			for (int j = 0; j < N; j++) {
				ans = Math.max(ans, benefit[i][j]);
			}
		}
		return ans;
	}
}