[SWEA 4012] 요리사 (Java)

SWEA 4012 요리사

문제풀이

삼성상시역테 기출 문제 중에서도 이렇게 두 팀을 나누는 문제가 있었던 것 같다. 그 때도 약했는데 지금도 상당히 멘붕이 왔었다. 침착하게 풀면 금방 풀것인데 어떤 방식으로 나눠볼까 고민하다가 시간이 너무 많이 흘렀다. 다음부터는 이 문제에서 사용한 방법만을 사용해야겠다.

• 두 팀으로 가르는 모든 경우의 수를 해본다.
• 팀 내에서 2가지 식재료를 뽑는 모든 조합을 한다.
• 두 팀의 차이가 가장 작은 것을 구한다.

각 식재료가 가질 수 있는 경우를 생각한다.

• A 음식에 속한다.
• B 음식에 속한다.

이 문제에서는 정확히 반으로 나누기 때문에 A, B에 속하는 식재료의 개수에 제한을 둔다. 어느 한쪽으로 모두 쏠려도 되는 경우라면 개수 제한을 풀면된다. 또는 모든 팀에 반드시 한 개 이상은 있어야한다면 미리 한 원소를 넣고 시작하거나 개수 제한을 원소 총 개수 - 1으로 주면 되겠다.

if(sizeA < N / 2) {
	A.add(idx);
	divide(idx + 1);
	A.remove(A.size() - 1);
}

if(sizeB < N / 2) {
	B.add(idx);
	divide(idx + 1);
	B.remove(B.size() - 1);
}

구현코드

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

public class Solution {
	
	static int[][] synergy;
	static ArrayList<Integer> A, B;
	static int N, T;
	static long foodA, foodB, 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) {
			
			N = Integer.parseInt(br.readLine());
			
			synergy = new int[N + 1][N + 1];
			A = new ArrayList<>();
			B = new ArrayList<>();
			ans = Long.MAX_VALUE;
			
			for(int r = 1 ; r <= N ; ++r) {
				st = new StringTokenizer(br.readLine());
				for(int c = 1 ; c <= N ; ++c) {
					synergy[r][c] = Integer.parseInt(st.nextToken());
				}
			}
			
			divide(1);
			
			
			System.out.println("#" + t + " " + ans);
		}
	}

	private static void divide(int idx) {
		if(idx > N) {
			foodA = 0;
			foodB = 0;
			cook(true, 0, 0, new int[2]);
			cook(false, 0, 0, new int[2]);
			
			long gap = Math.abs(foodA - foodB);
			
			ans = ans > gap ? gap : ans;
			
			return;
		}
		
		int sizeA = A.size();
		int sizeB = B.size();
		
		if(sizeA < N / 2) {
			A.add(idx);
			divide(idx + 1);
			A.remove(A.size() - 1);
		}
		
		if(sizeB < N / 2) {
			B.add(idx);
			divide(idx + 1);
			B.remove(B.size() - 1);
		}
	}

	private static void cook(boolean isA, int cnt, int idx, int[] indexs) {
		ArrayList<Integer> list = isA ? A : B;
		
		if(cnt == 2) {
			if(isA) {
				foodA += synergy[indexs[0]][indexs[1]];
				foodA += synergy[indexs[1]][indexs[0]];
			} else {
				foodB += synergy[indexs[0]][indexs[1]];
				foodB += synergy[indexs[1]][indexs[0]];
			}
			
			return;
		}
		
		for(int i = idx ; i < list.size() ; ++i) {
			indexs[cnt] = list.get(i);
			cook(isA, cnt + 1, i + 1, indexs);
		}
	}
}