https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu
📌 최종코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class SWEA2115_벌꿀채취 {
static int T;
//배열크기
static int N;
//꿀 영역 크기
static int M;
//꿀 용량
static int C;
static int mat[][];
//꿀범위로 할 2가지 고를 때 첫번쨰 고르고 visited에 표시하여 두번쨰 못 고르게 함
static int visited[][];
//고른 2개의 영역을 가지고 중복조합을 돌기 위한 visited
static int chosenHoneyVisited[];
//2개의 영역 저장을 위한 배열
static int[][] choosed;
//2번째 영역을 고르다가 더 이상 못고르면 available을 false로 하고 그만 탐색하게끔 함
static boolean available;
static int ansFirst;
static int ansSecond;
static int ansFinal;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
T = Integer.parseInt(br.readLine());
for (int t = 1; t < T + 1; t++) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
mat = new int[N][N];
visited = new int[N][N];
choosed = new int[2][M];
chosenHoneyVisited = new int[M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
mat[i][j] = Integer.parseInt(st.nextToken());
}
}
choose();
System.out.println("#" + t + " " + ansFinal);
ansFinal = 0;
}
}
private static void choose() {
for (int i = 0; i < N; i++) {
for (int j = 0; j <= N-M; j++) {
for (int j2 = 0; j2 < M; j2++) {
choosed[0][j2] = mat[i][j+j2];
visited[i][j+j2] = 1;
}
for (int i2 = 0; i2 < N; i2++) {
for (int j3 = 0; j3 <= N-M; j3++) {
available = true;
for (int j4 = 0; j4 < M; j4++) {
if(visited[i2][j3+j4]==1) {
available = false;
break;
}
choosed[1][j4] = mat[i2][j3+j4];
}
if(available) {
chooseHoney(choosed[0], new int[M], 0, 0,0);
chooseHoney(choosed[1], new int[M], 0, 0,1);
if(ansFirst+ansSecond > ansFinal) {
ansFinal = ansFirst+ansSecond;
}
ansFirst = 0;
ansSecond = 0;
}
}
}
}
}
}
private static void chooseHoney(int[] choosed, int res[], int level, int begin, int choosedIdx) {
if(level == M) {
int sum = 0;
for (int i = 0; i < res.length; i++) {
if(res[i]==1) sum+=choosed[i];
}
if(sum<=C) {
int calRes = cal(res, choosed);
if(choosedIdx == 0) {
ansFirst = Math.max(ansFirst, calRes);
}
else
ansSecond = Math.max(ansSecond, calRes);
}
}
else {
for (int i = begin; i < M; i++) {
if(chosenHoneyVisited[i]==0) {
chosenHoneyVisited[i]=1;
res[level] = 1;
chooseHoney(choosed, res, level+1, i+1, choosedIdx);
res[level] = 0;
chosenHoneyVisited[i]=0;
chooseHoney(choosed,res,level+1,i+1, choosedIdx);
}
}
}
}
private static int cal(int[] res, int[] choosed) {
int ans = 0;
for (int i = 0; i < res.length; i++) {
if(res[i]==1) {
ans+=Math.pow( choosed[i], 2);
}
}
return ans;
}
}
📌 풀이
먼저 영역을 두 개로 나누기 위해서 choose함수를 부르고 choose()에서는 정한 두개의 영역을 꿀의 범위에 따라서 또 2개로 나누기 위하여 각 영역마다 chooseHoney를 부른다.
중요한 건 choose 함수에서 첫번째 영역이 어디냐에 따라서 두번째 영역으로 설정할 수 있는 범위의 개수가 달라지므로, 첫번째 영역을 정한 상태에서 visited 배열에 첫번째 영역 부분을 표시하고, 그 visited를 거치지 않을 때에만 2번째 영역으로 정하고 chooseHoney함수를 부르도록 하였다.
private static void chooseHoney(int[] choosed, int res[], int level, int begin, int choosedIdx) {
if(level == M) {
int sum = 0;
for (int i = 0; i < res.length; i++) {
if(res[i]==1) sum+=choosed[i];
}
if(sum<=C) {
int calRes = cal(res, choosed);
if(choosedIdx == 0) {
ansFirst = Math.max(ansFirst, calRes);
}
else
ansSecond = Math.max(ansSecond, calRes);
}
}
else {
for (int i = begin; i < M; i++) {
if(chosenHoneyVisited[i]==0) {
chosenHoneyVisited[i]=1;
res[level] = 1;
chooseHoney(choosed, res, level+1, i+1, choosedIdx);
res[level] = 0;
chosenHoneyVisited[i]=0;
chooseHoney(choosed,res,level+1,i+1, choosedIdx);
}
}
}
}정해진 영역을 가지고 직접적인 꿀 채취할 곳을 정할때는 부분집합과 백트래킹을 사용하였다. 먼저 모든 중복조합 경우를 구한 다음, [0,0,1,1,1] 과 같이 res가 나오면 1인 인덱스에 해당하는 영역의 값을 더한다.
더한 값이 C 즉, 꿀통의 범위를 벗어나면 그 영역의 꿀 선택 경우의 수는 고려하지 않고 넘어간다.
문제를 풀 때만 해도 꿀을 채취할 곳을 정하는 것을 부분집합으로 구했음에도 중복조합으로 구한다고 생각했다. 중복조합도 한번 정리할 필요가 있을 듯 하다.
Reference
부분집합 레퍼런스
https://bcp0109.tistory.com/17
중복조합
https://velog.io/@cgw0519/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%88%9C%EC%97%B4-%EC%A4%91%EB%B3%B5%EC%88%9C%EC%97%B4-%EC%A1%B0%ED%95%A9-%EC%A4%91%EB%B3%B5%EC%A1%B0%ED%95%A9-%EC%B4%9D%EC%A0%95%EB%A6%AC
