백준 14889번 - 스타트와 링크

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

[풀이]

1. N명 중 N/2명을 골라서 팀을 짠다.

 - 조합

 - 비트마스킹으로 구현했는데 그냥 배열로 해도 속도 차이 없을 것 같다.

 

2. 1번에서 만든 팀과 나머지 인원 팀의 능력치 합을 각각 구하고, 두 능력치의 차이를 구한다.

인풋으로 주어지는 2차원 배열 arr를 모두 탐색하면서 i,j가 팀에 속할 경우 arr[i][j] 값을 능력치 합에 더하면 된다.

 

3. 1~2번을 반복하여 두 팀의 능력치의 차이의 최소값을 구한다.

 

[소스코드]

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

public class Main{
    static int n;
    static int[][] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        String str=null;
        StringTokenizer st=null;

        n=Integer.parseInt(br.readLine());
        arr=new int[n+1][n+1];
        for(int i=1;i<=n;i++) {
            str = br.readLine();
            st = new StringTokenizer(str);
            for (int j = 1; j <= n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        boolean[] chk=new boolean[n+1];
        int result=game(chk,0,0,1);
        bw.write(result+"");

        bw.flush();
        bw.close();
        br.close();
    }
    public static int game(boolean[] chk, int bit, int cnt, int idx){
        if(cnt==(n/2)){
            int startScore=getScore(bit);
            int linkScore=getScore(~bit);
            return startScore>linkScore?(startScore-linkScore):(linkScore-startScore);
        }
        if(idx>n){
            return Integer.MAX_VALUE;
        }
        int result=Integer.MAX_VALUE;
        for(int i=idx;i<=n;i++){
            if(chk[i]){
                continue;
            }
            chk[i]=true;
            int tbit=bit|(1<<i);
            int tmpResult=game(chk,tbit,cnt+1,i+1);
            result=Math.min(result,tmpResult);
            chk[i]=false;
        }
        return result;
    }
    public static int getScore(int bit){
        int sum=0;
        for(int i=1;i<=n;i++){
            if((bit&(1<<i))==0){
                continue;
            }
            for(int j=1;j<=n;j++){
                if((bit&(1<<j))>0){
                    sum+=arr[i][j];
                }
            }
        }

        return sum;
    }
}