[알고리즘/SWEA] #4012 요리사

package algorithm_lab.day10.q2;

import java.util.Arrays;
import java.util.Scanner;

public class SWEA_4012 {
	
	public static int[][] s;
	public static int N,Min;
	public static int[] select1,select2;
	public static boolean[] used;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		
		int T = sc.nextInt();
		
		for(int t=1;t<=T;t++) {
			
			N = sc.nextInt();
			s=new int[N][N];
			select1= new int[N/2];
			select2= new int[N/2];
			used = new boolean[N];
			Min =Integer.MAX_VALUE;
			for(int i=0;i<N;i++) {
				for(int j=0;j<N;j++) {
					s[i][j]=sc.nextInt();
				}
			}
			comb(0,0);
			sb.append("#").append(t).append(" ").append(Min).append("\n");
		}
		System.out.print(sb.toString());
	}
	
	public static void comb(int cnt,int start) {
		//기저조건
		if(cnt==N/2) {
			//select2 채우기
			int idx = 0;
			for(int i = 0; i <N; i++) {
				if(!used[i]) select2[idx++] = i;
			}
			//select1 요리의 합
			int sum1=0;
			for(int i=0;i<N/2;i++) {
				for(int j=0;j<N/2;j++) {
					sum1+=s[select1[i]][select1[j]];
				}
			}
			//select2 요리의 합
			int sum2=0;
			for(int i=0;i<N/2;i++) {
				for(int j=0;j<N/2;j++) {
					sum2+=s[select2[i]][select2[j]];
				}
			}
			//최솟값구하기
			if(Min>Math.abs(sum1-sum2)) Min=Math.abs(sum1-sum2);
			return;
		}
		//select1조합
		for(int i=start;i<N;i++) {
			select1[cnt]=i;
			used[i]=true;
			comb(cnt+1,i+1);
			used[i]=false;
		}
	}
}