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

1. team을 이룰 수 있는 모든 경우의 수를 생각한다 (team은 1명 이상이며, 양쪽 숫자가 맞지 않아도 된다.)
2. team1이 결성 되면 나머지 값은 team2가 된다.
3. team1, team2의 능력치에 대해 최소값을 찾는다.

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
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, int length) {
    	// 팀이 완성 되었을때 리턴
		if(idx == length) {
        
        	// 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, length);
		}

	}
	
	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;
				}
			}
		}


		// 1명 이상은 팀이 되어야함
		for (int i = 1 ; i < n; i++) {
			team1 = new int[i];
			team2 = new int[n-i];
			recursive(0, 0, s, i);	
		}
		
		
		System.out.print(result);
		
	}

}