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

문제

www.acmicpc.net/problem/15661

15661번: 링크와 스타트

 

풀이

 스타트와 링크 문제와 달라진 점은 팀을 N/2 N/2로 나누지 않고 각 팀의 수를 다르게 나눠도 된다는 거다. 즉 N=4이라 했을 때 가능한 팀원 수(스타트팀, 링크팀)는 (1,3) (2,2) (3,1)이다.

 

 따라서 이 문제도 스타트팀을 기준으로 생각하면 된다. 스타트팀에 1명을 뽑았다면, 링크팀은 3명이고 그 멤버는 스타트팀이 아닌 사람이다. 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
/*
두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 한다.
-> 스타트팀을 뽑는다 1명~ N-1명
 */
public class Main {
    static int N;
    static int[][] ability;

    static int[] startTeam;
    static int[] linkTeam;
    static boolean[] isStartTeam;
    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;

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

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

        for(int pickCount = 1; pickCount<=N-1; pickCount++){
            startTeam = new int[pickCount];
            linkTeam = new int[N-pickCount];
            isStartTeam = new boolean[N+1];
            pickStartTeam(pickCount, 0  , 0);
        }

        bw.write(String.valueOf(min));
        bw.flush();
    }

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

            // 능력 차 구하기
            int startTeamAbility = 0;
            int linkTeamAbility = 0;
            for(int k = 0; k<startTeam.length;k++){
                for(int j = 0; j<startTeam.length; j++){
                    startTeamAbility+= ability[startTeam[k]][startTeam[j]];
                }
            }

            for(int k = 0; k<linkTeam.length; k++){
                for(int j = 0; j<linkTeam.length; j++){
                    linkTeamAbility+= ability[linkTeam[k]][linkTeam[j]];
                }
            }

            int gap = Math.abs(startTeamAbility-linkTeamAbility);
            min = Math.min(min, gap);

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

                pickStartTeam(pickCount, number, index+1);
                isStartTeam[number] = false;
            }
        }
    }
}