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

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

SW Expert Academy

---

1. 문제 요약

NxN 크기의 map에서

1. 일꾼 2명이 가로 M 길이의 벌꿀을 선택한다

2. 선택한 각각의 꿀에서 구할 수 있는 합이 C보다 작을 때, 총 수익(각각 제곱하여 더함)을 출력한다.

[제약조건]

하나의 벌통에서 일부분의 꿀만 채취할 수 없다. 즉, 한 칸에 들어있는 숫자가 9면 9를 그대로 더해야 한다.

 

2. 풀이

조합 + 부분집합 문제이다.

1. 일꾼 2명이 벌꿀을 선택할 때 조합을 사용했다.

 - N=4라면 0~15까지의 숫자 중 각각 하나를 선택한다. 선택한 두 숫자는 tgt[ ] 안에 담아준다.

 - 기저조건에서,

     => 선택한 숫자의 y좌표와 가로M길이 끝(선택한 숫자+M-1)의 y좌표가 서로 다르면 return한다.

           (첫 번째, 두 번째 둘 다)

     => 첫 번째 선택한 숫자의 가로 M길이 끝 숫자(선택한 숫자+M-1)가 두 번째 선택한 숫자보다 크거나 같으면 return한다.

2. 일꾼 2명의 벌꿀을 각각 선택했으니, 이제 최대 합을 구하러 간다. 최대합은 개수마다 모든 조합을 보고 최댓값을 갱신하였기 때문에, 부분집합을 사용했다.

 - 일꾼1, 일꾼2 각각 부분집합을 돌려주었고 부분집합이 끝나고 나온 최대합을 서로 더해주었다.

 - 이것을 모든 조합에 대해 또 최댓값을 갱신해주었다.

* 부분집합의 기저조건으로 합이 C보다 클 경우, return 한다.

 

3. 코드

import java.io.*;
import java.util.*;

public class SW_2115_벌꿀채취 {

	static int[][] map;
	static int N, M, C, ans, honeyMax0, honeyMax1;
	static int[] tgt;
	static boolean[] isSelected;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int T = Integer.parseInt(br.readLine());
		for (int tc=1; tc<=T; tc++) {
			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];
			tgt = new int[2];
			
			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());
				}
			}// 입력 끝
			
			ans=0;
			comb(0,0);
			System.out.println("#"+tc+" "+ans);
		}
	}
	
	static void comb(int tgtIdx, int srcIdx) {
		if (srcIdx==N*N) return;
		if (tgtIdx==2) {
			
			if ( tgt[0]+M-1 >= tgt[1] ) return;
			if ( ( tgt[0]/N != (tgt[0]+M-1)/N ) || ( tgt[1]/N != (tgt[1]+M-1)/N ) ) return;
			
			int res = getMaxHoney();
			ans = Math.max(ans, res);
			
			return;
		}
		tgt[tgtIdx] = srcIdx;
		comb(tgtIdx+1, srcIdx+1);
		comb(tgtIdx, srcIdx+1);
	}
	
	static int getMaxHoney() {
		honeyMax0 = 0;
		isSelected = new boolean[N*N];
		subset(0, tgt[0], tgt[0]+M, 0, 0);
		honeyMax1 = 0;
		isSelected = new boolean[N*N];
		subset(1, tgt[1], tgt[1]+M, 0, 0);
		
		return honeyMax0 + honeyMax1;
	}
	
	static void subset(int mode, int idx, int end, int sum, int powSum) {
		if (sum > C) return;
		if (idx == end) {
			if (mode==0) {
				honeyMax0 = Math.max(honeyMax0, powSum);
			} else if (mode == 1) {
				honeyMax1 = Math.max(honeyMax1, powSum);
			}
			return;
		}
		
		int y = idx/N;
		int x = idx%N;
		
		isSelected[idx] = true;
		subset(mode, idx+1, end, sum+map[y][x], powSum+map[y][x]*map[y][x]);
		isSelected[idx] = false;
		subset(mode, idx+1, end, sum, powSum);
		
	}
}