[java] sw expert academy - 벌꿀 채취

문제

SWEA - 벌꿀 채취
각 벌통에 있는 꿀의 양이 주어졌을 때, 일꾼 두명이 벌꿀을 채취해서 얻을 수 있는 최대 수익을 구하는 문제

제한사항

벌통들의 크기 N : 3 <= N <= 10
선택할 수 있는 벌통의 수 M : 1 <= M <= 5
꿀을 채취할 수 있는 최대 양 C : 10 <= C <= 30
하나의 벌통에서 채취할 수 있는 양 : 1 이상, 9 이하

풀이

두 명의 일꾼이 높이 1, 가로 M의 벌통을 각각 선택한 다음, 수익의 합이 최대인 경우를 구하는 문제다

먼저 각 일꾼이 벌통을 선택하는 부분은 이중 for를 사용했다
첫번째 일꾼이 i, j를 선택한다 (i행의 j열부터 j+M열까지 선택)
두번째 일꾼이 r, c를 선택한다 (r행의 c열부터 c+M열까지 선택)

이때 첫번째 일꾼이 선택한 벌통과 두번째 일꾼이 선택한 벌통이 겹치면 안되니까 조건을 건다
먼저선택한 i,j 를 이용해서 r, c의 범위를 잡는다

for (int r = i; r < N; r++) { 
	for (int c = i == r ? j + M : 0; c <= N - M; c++) {
		...

첫번째 일꾼이 (i, j) ~ (i, J + M)을 선택했을 때
두번째 일꾼이 (i, j + M) ~ (i, ~ N)의 열을 선택할 수 있으니까
행이 같으면 c = j + M, 다르면 c = 0부터 시작한다

이때 각 일꾼이 선택한 벌통에서 계산한 최대 값은 memo 배열을 사용해서 저장한다
계산 결과가 없으면, 계산한 값을 저장해서 다음에 쓸 수 있게 했다

최대값 계산은 선택한 벌통(배열)의 합이 C 이하인지 확인한다
C 이하인 경우, 전체 벌통에서 채취가 가능하므로 각 벌통 값을 제곱해서 더해준다
C 초과인 경우, 선택한 벌통에서 일부를 뽑아 C를 넘지 않으면서 이익이 최대일 때를 계산한다

private static int subsum(int x, int y, int idx, int val, int total) {
	if (idx == M) {
		return total;
	}
	int n = map[x][y + idx]; // 채취할 꿀의 양
	int selected = val + n <= C ? subsum(x, y, idx + 1, val + n, total + (n * n)) : 0; // C를 넘으면 안되니까 넘지않는다면 진행
	int nonselected = subsum(x, y, idx + 1, val, total); // 선택 안했을 경우
	return Math.max(selected, nonselected);
	}

x : 행
y : y + idx 열 idx : M개까지 선택을 확인하기 위한 수
val : 벌꿀에서 채취할 수 있는 양의 합
total : 선택한 벌통의 제곱의 합

부분집합을 구할 때 방식처럼 해당 벌통을 선택했을 떄, 안했을 때 각각을 구해서 큰 값을 리턴한다

M, N이 작은 범위여서 완탐 ~~!

소스코드

// 패키지 생략

public class b2115_벌꿀채취 {

	private static int C,M,N;
	private static int[][] map;
	private static int[][] memo;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int TC = Integer.parseInt(br.readLine());
		int ans = 0;
		StringTokenizer st;
		for (int tc = 1; tc < TC + 1; tc++) {
			ans = 0;
			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];
			memo = new int[N][N];
			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++) {
				Arrays.fill(memo[i], -1);
			}
			// start
			for (int i = 0; i < N; i++) {
				for (int j = 0; j <= N - M; j++) {
					for (int r = i; r < N; r++) {
						for (int c = i == r ? j + M : 0; c <= N - M; c++) {
							int first = memo[i][j] == -1 ? memo[i][j] = getMaxProfit(i, j) : memo[i][j];
							int second = memo[r][c] == -1 ? memo[r][c] = getMaxProfit(r, c) : memo[r][c];
							ans = Math.max(ans, first + second);
						}
					}
				}
			}
			// end
			System.out.println("#" + tc + " " + ans);
		}
	}

	private static int getMaxProfit(int x, int y) {
		int[] v = new int[M];
		int total = 0;
		int result = 0;
		for (int i = 0; i < M; i++) {
			v[i] = map[x][y + i];
			total += v[i];
		}
		if (total <= C) {
			for (int i = 0; i < v.length; i++) {
				result += v[i] * v[i];
			}
			return result;
		} else {
			result = subsum(x, y, 0, 0, 0);
			return result;
		}
	}

	private static int subsum(int x, int y, int idx, int val, int total) {
		if (idx == M) {
			return total;
		}
		int n = map[x][y + idx];
		int selected = val + n <= C ? subsum(x, y, idx + 1, val + n, total + (n * n)) : 0;
		int nonselected = subsum(x, y, idx + 1, val, total);
		return Math.max(selected, nonselected);
	}
}