[알고리즘/백준] #14889 스타트와 링크

난이도: Silver2
문제) 스타트와 링크

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

public class Main{
	
	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();
		
        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);
        System.out.print(Min);
	}
	
	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;
		}
	}
}