백준 14889 스타트와 링크(java)

백트래킹을 통해 스타트 팀의 인원을 N/2만큼 조합해서 골라주고, 나머지인원은 링크팀으로 할당한다.

전체 인원을 다 기록한 것을 인자를 통해 확인되면 차이가 몇 나는지 확인해준다.

 

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

public class Main {
    /*
    짝수인원수 받아서 반갈라서 하는거니까,절반 뽑아서 스타트 팀에 박고 나머지 링크에 넣고
    쭉 돌면서 최소 찾아내자. 더하다가 전 최소값을 넘기면 가지치기?
     */
    static int n;
    static int[][] arr;
    static int result = Integer.MAX_VALUE;
    static boolean[] startbool = new boolean[21];
    static int[] startteam = new int[21];
    static int[] linkteam = new int[21];
    static void solve(int startcount, int fornum,int tempsum){
        if(startcount==n/2){
            for(int i=0,j=0;i<n;i++){
                 if(!startbool[i])
                 {
                     linkteam[j++]=i;
                 }
            }
            int linkteamsum=0;
            for(int i=0;i<n/2;i++){
                for(int j=i+1;j<n/2;j++){
                    linkteamsum+= arr[linkteam[i]][linkteam[j]];
                    linkteamsum+= arr[linkteam[j]][linkteam[i]];
                }
                if(linkteamsum-tempsum>result) return;
            }
            if(Math.abs(linkteamsum-tempsum)<result) result = Math.abs(linkteamsum-tempsum);
            //System.out.println("스타트는"+startteam[0]+startteam[1]+startteam[2]+" 결과는"+ Math.abs(linkteamsum-tempsum)+" tempsum:"+tempsum+"linkteamsum:"+linkteamsum);
        }

        for(int i=fornum;i<n;i++){
            startbool[i]=true;
            startteam[startcount]=i;
            int nowsum=0;
            for(int j=0;j<startcount;j++){
                //나랑 지금까지의 팀목록과 매칭.
                nowsum+=arr[startteam[j]][i];
                nowsum+=arr[i][startteam[j]];

            }
            solve(startcount+1,i+1,tempsum+nowsum);
            startbool[i]=false; // 그러면 true이면 스타트고 false면 링크팀
        }

    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n=Integer.parseInt(br.readLine());
        arr = new int[21][21];
        String str ="";
        Arrays.fill(startbool,false);
        for(int i=0;i<n;i++){
            str = br.readLine();
            StringTokenizer token = new StringTokenizer(str);
            for(int j=0;j<n;j++){
                arr[i][j]=Integer.parseInt(token.nextToken());
            }
        }
        solve(0,0,0);
        System.out.println(result);
    }
}

설계를 너무 복잡하게 해서 배열 인덱스에 들어갈 것이 너무 헷갈려서 시행착오를 계속 한 코드.

배열 이름 제대로 정하고 for문 인덱스를 써야할지 그 인덱스로 다른 배열에 접근해야 할지 잘 생각하자