[SWEA 2115] 벌꿀채취 (Java)

SWEA 2115 벌꿀채취

문제풀이

재귀를 통해 일꾼 1, 2가 벌통을 채취하는 모든 경우를 구하고 각 경우에 대해서 이윤을 산출하고 그 중 최댓값을 출력하면 된다.

• 2차원 형태에서의 순서와 중복이 없는 조합이라고 보면 되는데 일꾼1이 선택한 벌통 이후의 벌통부터 일꾼2가 선택하도록 해야한다. 이 때 일꾼1이 선택한 좌표를 해시값으로 만들어 넘겨주고 일꾼2가 선택할때는 해당 좌표를 해시값으로 만들어 인자로 넘어온 해시값 초과할 때 부터 선택할 수 있게 하면 된다.
  • r * 100(max(R, C) 보다 큰 값) + c
• 선택한 벌통들을 정렬하고 가장 많은 벌꿀부터 채취하는 그리디방식을 생각했지만 테스트케이스상에서 통과 못하는 것들이 있었고 가장 높은 이윤을 낼 수 있는 조합을 찾아내야했다.

구현코드

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

public class Solution {

	static int[][] map;
	static boolean[][] selected;
	static boolean[] selected2;
	static int[][] worker;
	static int[] income;
	static int N, M, C, T, ans;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null; 
		
		T = Integer.parseInt(br.readLine());
		
		for(int t = 1 ; t <= T ; ++t) {
			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];
			selected = new boolean[N][N];
			selected2 = new boolean[M];
			worker = new int[2][M];
			ans = 0;
			
			for(int r = 0 ; r < N ; ++r) {
				st = new StringTokenizer(br.readLine());
				for(int c = 0 ; c < N ; ++c) {
					map[r][c] = Integer.parseInt(st.nextToken());
				}
			}
			
			selectHoneyComb(0, -1);
			
			System.out.println("#" + t + " " + ans);
		}
	}

	private static void selectHoneyComb(int idx, int pos) {
		if(idx == 2) {
			// 벌통 선택 완료 수익 계산
			int total = 0;
			income = new int[2];
			
			for(int i = 0 ; i < 2 ; ++i) {
				findHighestIncome(i, 0, 0);
				total += income[i];
			}
			 
			ans = total > ans ? total : ans;
			
			return;
		}
		
		for(int r = 0 ; r < N ; ++r) {
			for(int c = 0 ; c < N ; ++c) {
				// 이전 좌표는 선택 안함  
				if(r * 100 + c <= pos) continue;
				// 가로로 놓을 수 없거나 이미 선택된 벌통은 제외 
				if(c + M - 1 >= N || selected[r][c]) continue;
				
				// 벌통 선택
				for(int i = 0 ; i < M ; ++i) {
					selected[r][c + i] = true;
					worker[idx][i] = map[r][c + i];
				}

				selectHoneyComb(idx + 1, r * 100 + c);
				
				// 벌통 선택 해제
				for(int i = 0 ; i < M ; ++i) {
					selected[r][c + i] = false;
				}
			}
		}
	}

	private static void findHighestIncome(int idx, int sum, int money) {
		income[idx] = money > income[idx] ? money : income[idx];
		
		for(int i = 0 ; i < M ; ++i) {
			if(selected2[i]) continue;
			
			if(sum + worker[idx][i] <= C) {
				selected2[i] = true;
				findHighestIncome(idx, sum + worker[idx][i], money + worker[idx][i] * worker[idx][i]);
				selected2[i] = false;
			}
		}
	}
}