SWEA 4012 요리사

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

public class Solution {
	static int[][] synergy;// 재료 간 시너지를 저장하는 배열
	static int[] ingreA;// A의 요리에 사용할 재료
	static int[] ingreB;// B의 요리에 사용할 재료
	static boolean[] ingredients;// 뽑은 재료와 안 뽑은 재료 나누기
	static int food;
	static int N;// 전체 재료의 개수
	static int min;// 완성된 두 요리의 최소 합
	static int cookA, cookB;// 각 요리의 시너지 합

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(in.readLine());// 테스트 케이스
		for (int t = 1; t <= T; t++) {
			N = Integer.parseInt(in.readLine());// 재료 개수
			ingreA = new int[N / 2];// 재료개수/2 각각 재료 저장할 배열 선언
			ingreB = new int[N / 2];
			ingredients = new boolean[N];// 전체 재료 뽑는 경우와 안 뽑는 경우 체크
			synergy = new int[N][N];
			cookA = 0;
			cookB = 0;
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(in.readLine());
				for (int j = 0; j < N; j++) {
					synergy[i][j] = Integer.parseInt(st.nextToken());// 재료별 시너지
				}
			}
			min = Integer.MAX_VALUE;// 최소값을 구할 거니까 최대값을 저장해둬
			combi(0, 0);
			System.out.println("#" + t + " " + min);
		}
	}
	private static void combi(int start, int count) {
		if (count == N / 2) {
			int cnt = 0;
			for (int i = 0; i < N; i++) {
				if (ingredients[i] == false) {// 안 뽑힌거
					ingreB[cnt] = i;
					cnt++;
				}
			}
			cookA = 0;
			cookB = 0;
			for (int i = 0; i < N / 2; i++) {
				for (int j = 0; j < N / 2; j++) {
					if (i == j)
						continue;
					cookA += synergy[ingreA[i]][ingreA[j]];
					cookB += synergy[ingreB[i]][ingreB[j]];
				}
			}
			min = min > Math.abs(cookA - cookB) ? Math.abs(cookA - cookB) : min;
			return;
		}
		for (int i = start; i < N; i++) {
			ingredients[i] = true;// 뽑은거
			ingreA[count] = i;// A 요리에 사용할 재료 저장 (count는 N/2까지 증가)
			combi(i + 1, count + 1);
			ingredients[i] = false;// i를 뽑고 그 경우 다 구하면 false로 바꾸자
		}
	}
}