문제 이해

축구를 위해 N명이 모였다(N은 짝수)

1팀당 N/2명으로 이루어지도록 팀을 나눌 것이다.
이 때 능력치가 주어지는데, $S_{ij}$는 i번 사람과 j번 사람이 같은 팀에 속했을 때의 i번째 사람의 능력치이다.
즉, i번째 사람과 j번째 사람이 한 팀에 속해있다면, 해당 팀은 $S_{ij}$와 $S_{ji}$를 모두 더해 주어 두 사람이 한 팀이 되었을 때의 능력치를 모두 더해주어야 한다.

두 팀의 능력치 차이를 최소로 만드려고 한다. 그렇게 팀을 구성하였을 경우 두 팀 능력치 차이의 최소값을 출력하는 문제이다.

---

문제 풀이

DP를 활용해 풀 수 있나 고민해보았지만, 결국 Brute Force 방법밖에 생각나지 않았다.

2개 Group을 만들고, A Group에 들어갔을 경우에는 visit[x]=true로 설정해두고, B Group에 들어갔을 경우 visit[x]=false로 설정한다.

이후 한 Group에 N/2명이 들어갔다면 반대 팀에도 자동으로 N/2명이 들어가 있을 것이므로 각 팀의 능력치를 더하여 두 팀 능력치 차이를 구하고, 이 중 최솟값을 답으로 하면 될 것이다.

---

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();

	static int N;
	static int[][] arr;
	static boolean[] visit;
	static int min = Integer.MAX_VALUE;
	
	static void rec(int idx, int count) {
		if(count==N/2) {
			// 1팀에 N/2명이 들어 있으므로, 팀 구성이 완료되었다.
			int team_start = 0;
			int team_link = 0;
			for (int i = 0; i < N - 1; i++) {
				for (int j = i + 1; j < N; j++) {
					if (visit[i] == true && visit[j] == true) {
                    // i번째 사람과 j번째 사람이 A group에 속해 있음
						team_start += arr[i][j];
						team_start += arr[j][i];
					}
					else if (visit[i] == false && visit[j] == false) {
                    // i번째 사람과 j번째 사람이 B Group에 속해 있음
						team_link += arr[i][j];
						team_link += arr[j][i];
					}
				}
			}
			
			min = Math.min(min, Math.abs(team_start-team_link));
			
			return;
		}
		
		for(int i = idx+1;i<N;i++) {
			if(!visit[i]) {
                // i번째 사람이 A Group에 속해 있다고 가정하고 실험
				visit[i] = true;
				rec(i, count+1);
				visit[i] = false;
			}
		}
	}
	
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		
		N = sc.nextInt();
		
		arr = new int[N][N];
		visit = new boolean[N];
		
		for(int i =0;i<N;i++) {
			for(int j =0;j<N;j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		
		visit[0] = true;
        // 무조건 0번째 사람은 A Group에 속해있다고 가정하자
		rec(0,1);
		
		System.out.println(min);
	}
	
	
	static class FastReader // 빠른 입력을 위한 클래스

---

결과