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

1. team을 이룰 수 있는 모든 경우의 수를 생각한다 (team = n/2명)
2. team1이 결성 되면 나머지 값은 team2가 된다.
3. team1, team2의 능력치에 대해 최소값을 찾는다.

구현한 코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

	static int[] team1;
	static int[] team2;
	static int n, result = Integer.MAX_VALUE;

	// team1를 제외 한 나머지 값을 team2에 등록
	static void teams() {
		int cnt = 0;
		for(int i = 0 ; i < n ; i++) {
			boolean is = true;
			for(int j = 0 ; j < team1.length ; j++) {
				if(i == team1[j]) {
					is = false;
					break;
				}
			}
			
			if(is) {
				team2[cnt++] = i;
			}
		}
	}

	static void recursive(int idx, int start, int[][] s) {
    	// 팀이 완성 되었을때 리턴
		if(idx == n/2) {
        
        	// tema1 의 능력치
			int sum1 = 0;
			for(int i = 0 ; i < team1.length ; i++) {
				for(int j = i ; j < team1.length ; j++) {
					if(i == j) {
						continue;
					}
					sum1 += s[team1[i]][team1[j]] + s[team1[j]][team1[i]];
				}
			}
			
			teams();
			
            // tems2의 능력치
			int sum2 = 0;
			for(int i = 0 ; i < team2.length ; i++) {
				for(int j = i ; j < team2.length ; j++) {
					if(i == j) {
						continue;
					}
					sum2 += s[team2[i]][team2[j]] + s[team2[j]][team2[i]];
				}
			}

			int max = Math.max(sum1, sum2);
			int min = Math.min(sum1, sum2);

			// 능력치 차이가 최소인 경우를 리턴
			result = Math.min(result, max-min);
			return;
		}

		for(int i = start ; i < n ; i++) {
				team1[idx] = i;
				recursive(idx+1, i+1, s);
		}

	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());

		int[][] s = new int[n][n];
		for(int i = 0 ; i < n ; i++) {
			String[] arr =  br.readLine().split(" ");
			for(int j = 0 ; j < n ; j++) {
				s[i][j] = Integer.parseInt(arr[j]);
				if(i == j) {
					s[i][j] = 0;
				}
			}
		}

		team1 = new int[n/2];
		team2 = new int[n/2];
		recursive(0, 0, s);
		
		
		System.out.print(result);
	}
}