[Java] swea 2115 벌꿀채취

[Java] swea 2115 벌꿀채취

 

 

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu&categoryId=AV5V4A46AdIDFAWu&categoryType=CODE&problemTitle=sw&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2

SW Expert Academy

 

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

public class 모의SW_2115_벌꿀채취 {
	static int N, M, C, MAX;
	static int[][] map;
	static int[][] money;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int testcase = 1; testcase <= T; testcase++) {
			MAX = 0;
			StringTokenizer 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];
			money = new int[N][N-M+1];
			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());
				}
			}
			
			solve();
			for (int x = 0; x < N; x++) {
				for (int y = 0; y < N-M+1; y++) {
					int sum = money[x][y];
					for (int i = x; i < N; i++) {
						for (int j = 0; j < N-M+1; j++) {
							if(x == i && Math.abs(y-j) < M) continue;
							
							if(MAX < sum + money[i][j]) MAX = sum + money[i][j];
						} //j
					}//i
					
				}// y
			}//x
			
			System.out.println("#" + testcase  + " " + MAX);
		} //tc
		
	} //main

	private static void solve() {
		for (int i = 0; i < N; i++) {
			int order = 0;
			for (int j = 0; j <= N-M; j++) {
				int[] arr = new int[M];
				int idx = 0;
				for (int k = j; k < j+M; k++) {
					arr[idx++] = map[i][k];
				} // k

				moneyMAX = 0;
				getMAX(arr, 0, 0, 0);
				money[i][order] = moneyMAX;
				order++;
			} // j
		} // i
	} //solve
	
	static int moneyMAX;
	private static void getMAX(int[] arr, int cur, int sum, int zegopSum) {
		if(cur == arr.length) {
			if(moneyMAX < zegopSum) moneyMAX = zegopSum; 
			return;
		}
		
		if(sum + arr[cur] <= C)
			getMAX(arr, cur+1, sum+arr[cur], zegopSum+arr[cur]*arr[cur]);
		
		getMAX(arr, cur+1, sum, zegopSum);
	}
}

 

M개 연속으로 꿀통을 선택하여 최대 수익이 나오는 배열을 만들었다.

그게 getMax() 가 하는 일이다.

getMax 가 받는 일차원 배열은

위 그림에서 봤을 때 {6,1} , {8,5} 이런걸 받는 것..

일차원 배열을 받아서 6*6 + 1*1 이 가능한지(합이 C를 넘으면 안되므로), 안 된다면 어떤 벌꿀을 채취해야 수익이 큰 지 찾는다.

그리고 나서

가로로 슬라이드를 옮기면서 

money 배열에 입력한다.

마지막엔 money배열을 돌면서

두 개 배열을 뽑고 그 두 개 배열이 겹치지 않는지, 안 겹친다면 더했을 때 최대가 나오는지 확인한다.