[SWEA JAVA] 2115. [모의 SW 역량테스트] 벌꿀채취

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

SW Expert Academy

 

 

 

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

public class Solution {
	public static int T, N, M, C, ans = 0, cost1, cost2;
	public static int[][] map;
	public static int[][] MM;

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

		for (int tc = 1; tc <= T; tc++) {
			// 1. 입력받기
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());

			map = new int[N][N];
			MM = new int[N][N];
			ans = cost1 = cost2 = 0;

			// 1-1. map 입력받기
			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());
				}
			}

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N - M + 1; j++) {
					cost1 = 0;
					dfs(0,0,0,i,j);
					MM[i][j] = cost1;
				}
			}
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N - M + 1; j++) {
					for (int i2 = i; i2 < N; i2++) {
						int sj;
						if (i == i2) {
							sj = j + M;
						} else {
							sj = 0;
						}
						for (int j2 = sj; j2 < N - M + 1; j2++) {
							ans = Math.max(ans, MM[i][j] + MM[i2][j2]);
						}
					}
				}
			}
			
			// 2. 벌통 구하기
//			for (int i = 0; i < N; i++) {
//				for (int j = 0; j < N - M + 1; j++) {
//					cost1 = 0;
//					dfs(0, 0, 0, i, j);
//					cost2 = cost1;
//					for (int i2 = i; i2 < N; i2++) {
//						int sj;
//						if (i == i2) {
//							sj = j + M;
//						} else {
//							sj = 0;
//						}
//						for (int j2 = sj; j2 < N - M + 1; j2++) {
//							cost1 = 0;
//							dfs(0, 0, 0, i2, j2);
//							ans = Math.max(ans, cost1 + cost2);
//						}
//					}
//				}
//			}

			// 4. 출력하기
			System.out.println("#" + tc + " " + ans);

		}
	}

	public static void dfs(int n, int cnt, int sm, int ci, int cj) {
		if (cnt > C) { //
			return;
		}

		if (n == M) {
			cost1 = Math.max(cost1, sm);
			return;
		}

		dfs(n + 1, cnt + map[ci][cj + n], sm + map[ci][cj + n] * map[ci][cj + n], ci, cj);
		dfs(n + 1, cnt, sm, ci, cj);

	}

}