[Java] 백준 14889번 스타트와 링크

n/2명을 뽑는 조합을 구합니다.
구해진 조합으로 능력치 값을 더해주고 두 팀의 격차가 적은 값으로 갱신해줍니다.

모든 경우에 대해서 확인한 후 가장 격차가 적은 값을 출력해주었습니다.

import java.util.*;
import java.io.*;

public class Main {
  static int n;
  static int[][] arr;
  static boolean[] team;
  static int ans = Integer.MAX_VALUE;
    
  public static void main(String args[]) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      
    n = Integer.parseInt(br.readLine());
      
    arr = new int[n][n];
    team = new boolean[n];
      
    for(int i=0; i<n; ++i){
      StringTokenizer str = new StringTokenizer(br.readLine());
      for(int j=0; j<n; ++j){
        arr[i][j] = Integer.parseInt(str.nextToken());
      }
    }
      
    dfs(0, 0);

    System.out.println(ans);
  }
  static void dfs(int index, int cnt) {
    if(n / 2 == cnt){
      diff();
      return;
    }
    
    for(int i=index; i<n; ++i){
      team[i] = true;
      dfs(i+1, cnt+1);
      team[i] = false;
    }
  }
  
  static void diff() {
    int a = 0;
    int b = 0;
  
    for(int i=0; i<n-1; ++i){
      for(int j=i+1; j<n; ++j){
        if(team[i] == true && team[j] == true){
          a += arr[i][j];
          a += arr[j][i];
        } else if (team[i] == false && team[j] == false){
          b += arr[i][j];
          b += arr[j][i];
        }
      }
    }
    ans = Math.min(ans, Math.abs(a-b));
  }
}