[BOJ] 14889. 스타트와 링크

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

public class Main {
	static int N;
	static int arr[][];
	static int min=Integer.MAX_VALUE;
	static ArrayList<Integer> team1;
	static ArrayList<Integer> team2;
	public static void main(String[] args) {		
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		arr=new int[N][N];
		team1=new ArrayList<Integer>();
		team2=new ArrayList<Integer>();
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				arr[i][j]=sc.nextInt();
			} 
		}
		
		go(0);
		
		System.out.println(min);
		
	}
	
	public static void go(int index) {
		if(team1.size()>N/2 || team2.size()>N/2) {
			return;
		}
		if(index==N) {
			int diff=0;
			diff=Math.abs(calc(team1)-calc(team2));
			if(diff<min) min=diff;
		}
		team1.add(index);
		go(index+1);
		team1.remove(team1.size()-1);
		team2.add(index);
		go(index+1);
		team2.remove(team2.size()-1);
	}
	
	public static int calc(ArrayList<Integer> team) {
		int sum=0;
		for (int i = 0; i < N/2; i++) {
			for (int j = 0; j < N/2; j++) {
				if(i!=j) {
					sum+=arr[team.get(i)][team.get(j)];
				}
			}
		}
		return sum;
	}
}