https://www.acmicpc.net/problem/14889

축구를 하기위해 모인 n명을 n/2명씩 2팀으로 나눠서 각 팀의 능력치 합의 차이를 구해서
가능한 조합 수에서 최소 차이를 출력하는 문제이다.

풀이 아이디어

재귀를 활용해 n명을 두 팀으로 구성하는 모든 조합을 구한다.
그리고 그 조합에서 두 팀의 능력치 차이를 구한다.
능력치 차이값을 최소로 갱신하고 0이면 무조건 정답이므로 0을 출력하고 프로그램을 종료한다.

n명을 n/2명씩 나눈 경우의 수를 구하기
=> boolean[] select배열을 사용해 select[i]=true로 두면 i번째 팀원을 선택한 것으로 간주하고
member 변수를 이용해 선택한 팀원 수를 카운트해서 member==n/2면 n명 중 n/2명을 선택했을므로
true인 팀원은 team start에 더해주고
false인 팀원은 team link에 더해서 두 팀의 능력치합을 구한다.

배운 점

조합 (combination)을 재귀적으로 구현을 응용해서
$nCn/2$로 팀원을 선택하는 조합을 구할 수 있다는 걸 배우게 되었다.

또한 실행한 JAVA 프로그램을 종료하고 싶으면

System.exit(0);

이 명령어를 사용해 종료할 수 있다는 것도 배웠다.

풀이 코드

import java.util.*;
import java.io.*;
public class _14889 {
    static int n;
    static int[][] ability;
    static boolean[] select;
    static int minValue = Integer.MAX_VALUE;

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

        ability = new int[n][n]; // 팀원 i,j가 있을 때 향상되는 능력치
        select = new boolean[n+1]; // 팀원 조합의 선택 여부를 저장한 배열
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                ability[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        br.close();

        // N명 중에서 N/2명을 뽑는 모든 조합을 구한다.
        divideHalf(0, 0);
        System.out.println(minValue);
    }

    // 두 팀의 능력치 차이를 구하는 함수
    static void getAbilityDiff(){
        int teamStart = 0;
        int teamLink = 0;

        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                if(select[i] && select[j]){
                    teamStart += ability[i][j] + ability[j][i];
                }
                else if(select[i]==false && select[j]==false){
                    teamLink += ability[i][j] + ability[j][i];
                }
            }
        }
        int diff = Math.abs(teamStart - teamLink);
        // 차이가 0이면 무조건 정답이 되므로 0을 출력하고 종료
        if(diff==0){
            System.out.println(0);
            System.exit(0);
        }
        minValue = Math.min(minValue, diff);
    }

    // 두 팀으로 나눈 조합을 재귀적으로 구하는 함수
    static void divideHalf(int idx, int member){
        if(member == n/2){
            getAbilityDiff();
            return;
        }
        for(int i=idx;i<n;i++){
            if(select[i]==false){
                select[i]=true;
                divideHalf(i+1, member+1);
                select[i]=false;
            }
        }
    }
}