[모의 SW 역량테스트] 요리사

요리사

두 명의 손님에게 요리를 제공한다.

최대한 비슷한 맛의 요리를 제공해야 한다.

N개의 식재료를 N/2개씩 나누어 요리를 하려고 한다.

식재료 i는 j와 함께 요리하게되면 Sij의 시너지가 발생한다.

각 음식의 맛은 음식을 구성하는 식재료로 부터 발생하는 Sij들의 합이다.

N과 각 시너지들의 정보가 주어졌을 때, 두 음식간의 차이가 최소인 값을 출력해라.

---

풀이

• 조합을 두 번 사용한다.

1. 첫 조합은 N개에서 N/2개를 뽑는 것을 구현한다.

   • 배열에 뽑은 것을 저장한뒤 N/2를 뽑았다면 나머지 수를 저장할 배열을 생성해준다.

2. 다음 조합은 N/2에서 2개를 뽑는 모든 경우를 찾는다.

   • 뽑은 2개를 시너지를 저장한 배열의 주소로 사용한다.

   • 행과 열을 바꿀 때에도 누적해 준다.

   • 누적된 값은 1번의 결과에서 초기화 된다.

3. 1번에서 누적된 값들의 차이를 구한 뒤 최소값인지 판별한다.

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

public class Solution요리사 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		for(int tc = 1; tc <= T; tc++) {
			
			N = Integer.parseInt(br.readLine());
			
			arr = new int[N][N];
			
			for(int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for(int j = 0; j < N; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			ans = Integer.MAX_VALUE;
			com(0, 0, new int[N/2]);
			System.out.println("#"+tc+" "+ans);
		}

	}
	
	static int N;
	static int[][] arr;
	
	static int sum_A;
	static int sum_B;
	
	static int ans;
	
	static void com(int idx, int cnt, int[] food) {
		if(cnt == N/2) {
			int[] food_B = new int[N/2];
			boolean[] chk = new boolean[N];
			
			for(int i = 0; i < N/2; i++) {
				chk[food[i]] = true;
			}
			
			int index = 0;
			for(int i = 0; i < N; i++) {
				if(!chk[i]) {
					food_B[index] = i;
					index++;
				}
			}
			sum_A = 0;
			sum_B = 0;

			com2(0, 0, food, food_B, new int[2], new int[2]);

			ans = Math.min(ans, Math.abs(sum_A-sum_B));
			return;
		}
		if(idx >= N) {
			return;
		}
		
		food[cnt] = idx; 
		com(idx+1, cnt+1, food);
		food[cnt] = 0;
		com(idx+1, cnt, food);
		
	}
	
	
	static void com2(int idx, int cnt, int[] food, int[] food_B, int[] select_A, int[] select_B) {
		if(cnt == 2) {
			
			sum_A += arr[select_A[0]][select_A[1]];
			sum_A += arr[select_A[1]][select_A[0]];
			
			sum_B += arr[select_B[0]][select_B[1]];			
			sum_B += arr[select_B[1]][select_B[0]];			
			return;
		}
		if(idx >= food.length) {
			return;
		}
		select_A[cnt] = food[idx];
		select_B[cnt] = food_B[idx];
		com2(idx+1, cnt+1, food, food_B, select_A, select_B);
		com2(idx+1, cnt, food, food_B, select_A, select_B);
		
	}

}