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

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.Stack;

import java.util.StringTokenizer;

class Solution {

static boolean Debug = false;

static int MapSize, GetSize, Capacity;

static int[][] Map;

private static int MaxProfit;

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

BufferedReader br;

if (Debug) {

File f = new File("파일경로", "sample_input (3).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}

StringTokenizer st;

int T_Count = Integer.parseInt(br.readLine());

for (int T = 1; T <= T_Count; T++) {

// MapSize=4, GetSize=2, Capacity=13

st = new StringTokenizer(br.readLine());

MapSize = Integer.parseInt(st.nextToken());

GetSize = Integer.parseInt(st.nextToken());

Capacity = Integer.parseInt(st.nextToken());

// 지도데이터

Map = new int[MapSize][];

for (int i = 0; i < MapSize; i++) {

Map[i] = new int[MapSize];

st = new StringTokenizer(br.readLine());

for (int j = 0; j < MapSize; j++) {

Map[i][j] = Integer.parseInt(st.nextToken());

}

}

// 이용정보

MaxProfit = -1;

search();

System.out.println(String.format("#%d %d", T, MaxProfit));

}

}

private static void search() {

// 일꾼의 위치1, 위치2

int y1, x1, y2, x2;

for (int i = 0; i < MapSize * MapSize; i++) {

for (int j = i; j < MapSize * MapSize; j++) {

y1 = i / MapSize;

x1 = i % MapSize;

y2 = j / MapSize;

x2 = j % MapSize;

if (isRight(y1, x1, y2, x2) == false) {

continue;

}

// 계산하기

calculate(y1, x1, y2, x2);

}

}

}

private static void calculate(int y1, int x1, int y2, int x2) {

// 현재 좌표에서 최대의 벌꿀 수익량

int maxOne = 0, maxTwo = 0;

int one, two;

for (int i = 0; i < (1 << GetSize); i++) {

// Case (벌꾼 담기)

one = getProfit(y1, x1, i);

two = getProfit(y2, x2, i);

if (maxOne < one) {

maxOne = one;

}

if (maxTwo < two) {

maxTwo = two;

}

}

if(MaxProfit < maxOne + maxTwo) {

MaxProfit = maxOne + maxTwo;

}

}

private static Stack<Integer> pStack = new Stack<>();

private static int getProfit(int y, int x, int bitmask) {

int amount = 0;

for (int i = 0; i < GetSize; i++) {

// 현재 경우에서 일꾼 1의 수익량

if ((bitmask & (1 << i)) > 0) {

// i번째 꿀 수집

amount += Map[y][x + i];

pStack.push(Map[y][x + i]);

}

}

if (amount > Capacity) {

pStack.clear();

return 0;

} else {

int profit = 0;

int temp;

while (!pStack.isEmpty()) {

temp = pStack.pop();

profit += temp * temp;

}

return profit;

}

}

private static boolean isRight(int y1, int x1, int y2, int x2) {

if (y1 >= MapSize || y2 >= MapSize) {

// log("맵 사이즈 초과");

return false;

}

if (x1 + GetSize - 1 >= MapSize || x2 + GetSize - 1 >= MapSize) {

// log("맵 사이즈 초과");

return false;

}

int gap;

if (y1 == y2) {

gap = x1 - x2;

gap = gap > 0 ? gap : -gap;

if (gap < GetSize) {

return false;

}

}

return true;

}

private static void log(String input) {

if (Debug) {

System.out.println(input);

}

}

}