[백준 14889, Java] 스타트와 링크

문제

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

풀이

 우선 스타트 팀인 N/2 명을 뽑는다. 이 문제는 N과 M(2) 문제와 같다. 대신 boolean[] isStartTeam 배열을 선언해서, 스타트팀으로 뽑힌 사람의 번호를 true로 한다. 왜냐하면, 스타트 팀을 뽑으면 링크팀은 자동으로 나머지 사람이 되는데, 이때 스타트팀인지 아닌지를 구분하기 위해서이다. 

 

 스타트팀인 N/2명을 구했다면, 스타트팀이 아닌 N/2명을 링크팀으로 한다. 그런 다음 이중 for문을 이용해서 두팀의 능력치를 구한다. 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[][] ability;

    static boolean[] isStartTeam;
    static int[] startTeam;
    static int[] linkTeam;

    static int min;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        ability = new int[N+1][N+1];

        for(int r = 1; r<=N; r++){
            st = new StringTokenizer(br.readLine()," ");
            for(int c = 1; c<=N; c++){
                ability[r][c] = Integer.parseInt(st.nextToken());
            }
        }

        isStartTeam = new boolean[N+1];
        startTeam = new int[N/2];
        linkTeam = new int[N/2];

        min = Integer.MAX_VALUE;
        getGap(0,0);
        bw.write(String.valueOf(min));
        bw.flush();


    }
    public static void getGap(int beforeStartMember, int index){
        if(index>=N/2){
           //링크팀 구하기
            int i = 0;
            for(int number = 1; number<=N; number++){
                if(!isStartTeam[number]){
                    linkTeam[i] = number;
                    ++i;
                }
            }

            //능력치 구하기
            int startPotion = 0;
            int linkPotion = 0;
            for(int j = 0; j<startTeam.length; j++){
                for(int k = 0; k<startTeam.length; k++){
                    startPotion += ability[startTeam[j]][startTeam[k]];
                    linkPotion += ability[linkTeam[j]][linkTeam[k]];
                }
            }

            int gap = Math.abs(startPotion-linkPotion);
            min = Math.min(gap,min);

        }
        else{
            for(int nextMember = beforeStartMember+1; nextMember<=N; nextMember++){
                isStartTeam[nextMember] = true;
                startTeam[index] = nextMember;

                getGap(nextMember, index+1);
                isStartTeam[nextMember] = false;
            }
        }
    }
}