[swexpert] 4012. 요리사 (java)

 

import java.util.ArrayList;
import java.util.Scanner;

public class Solution {
		static int t,n;
		static int[][] table;
		static int answer;
		public static void main(String[] args) {
			Scanner sc=new Scanner(System.in);
			t=sc.nextInt();
			for (int tc = 1; tc <=t; tc++) {
				n=sc.nextInt();
				answer=Integer.MAX_VALUE;
				table=new int[n][n];
				for (int i = 0; i < n; i++) {
					for (int j = 0; j < n; j++) {
						table[i][j]=sc.nextInt();
					}
				}
				nCr(0,0,0);
				System.out.printf("#%d %d\n",tc,answer);
			}
			
		}
		
		private static void nCr(int cnt,int start,int flag) {
			if(cnt==n/2) {
				int sum1=0;
				int sum2=0;
				ArrayList<Integer> arr1=new ArrayList<>();
				ArrayList<Integer> arr2=new ArrayList<>();
				for (int i = 0; i < n; i++) {
					if((flag&1<<i)!=0)arr1.add(i);
					else {
						arr2.add(i);
					}
				}
				for (int i = 0; i < n/2; i++) {
					for (int j = i+1; j < n/2; j++) {
						int a=arr1.get(i);
						int b=arr1.get(j);
						sum1+=table[a][b];
						sum1+=table[b][a];
					}
				}
				for (int i = 0; i < n/2; i++) {
					for (int j = i+1; j < n/2; j++) {
						int a=arr2.get(i);
						int b=arr2.get(j);
						sum2+=table[a][b];
						sum2+=table[b][a];
					}
				}
				int temp=Math.abs(sum1-sum2);
				if(temp<answer)answer=temp;
				
				return;
			}
			for (int i = start; i < n; i++) {
				if((flag&1<<i)!=0)continue;
				nCr(cnt+1,i+1,flag|1<<i);
			}
			
		}
		
}