14889. 스타트와 링크

 

N x N 격자에 각 i 번호의 선수와 j 번호의 선수가 같은 팀 일때의 점수를 표기하고, 두 팀의 점수차가 최소가 되게 팀을 구성했을 때의 최소값을 출력하는 문제이다.

 

N의 수가 최대 20이라서 최악의 경우가 20명중에 10명뽑는 경우의 수가 된다. `20 C 10 = 184756` 이므로 브루트포스와 백트래킹을 쓰면 풀릴 것 같았다.

 

 

 

 

 

 

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

public class Main {
    public static int ans, N;
    public static int[][] MAP;
    public static boolean[] chk;

    public static void InputData() {
        try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
            N = Integer.parseInt(stk.nextToken());
            MAP = new int[N][N];
            chk = new boolean[N];
            ans = Integer.MAX_VALUE;

            for(int i = 0; i < N; i++){
                stk = new StringTokenizer(br.readLine(), " ");
                for(int j = 0; j < N; j++){
                    MAP[i][j] = Integer.parseInt(stk.nextToken());
                }
            }// N^2

        }catch (IOException e){
            e.printStackTrace();
        }
    } // 데이터 입력

    public static void Print_result(){
        try(BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))){
            bw.write(String.valueOf(ans));
            bw.flush();
        } catch (IOException e) {
            e.printStackTrace();
        }
    } // 결과 출력

    public static void solve(int ceil, int cnt, int idx){
        if(ceil == cnt){
            int A = 0, B = 0;
            for(int i = 0; i < N; i++){
                for(int j = i + 1; j < N; j++) {
                    if(chk[i] && chk[j]){
                        A += MAP[i][j] + MAP[j][i];
                    }else if(!chk[i] && !chk[j]){
                        B += MAP[i][j] + MAP[j][i];
                    }
                }
            }
            ans = Math.min(ans, Math.abs(A-B));
            return;
        }
        for(int i = idx; i < N; i++){
            if(chk[i])
                continue;

            chk[i] = true;
            solve(ceil, cnt + 1, i);
            chk[i] = false;
        }
    }

    public static void main(String[] args){
        InputData();
        solve(N/2, 0, 0);
        Print_result();
    }
}