스타트와 링크

📍 문제 설명

 

💡 접근

n명중에 2팀을 뽑아야하는데 여기서의 뽑히는 것의 구분은 boolean 값에 따라서 구별해준다.

n명의 상태 정보 값이 모두 필요하다.(뽑히는 경우와 뽑히지 않는 경우)

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, k;
    static int[][] board,dis;
    static int[] ch,pm;
    static boolean[] combi;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt();
        //m = kb.nextInt();
        board = new int[n][n];
        combi = new boolean[n];

        for(int i = 0; i < n; i++) {
            for(int j = 0 ; j < n; j++) {
                board[i][j] = kb.nextInt();
            }
        }
        //n명 중에 n/2명 뽑기
        //4명 중에 2명 뽑기
        //6명 중에 3명 뽑기
        //반으로 나눠서 스타트 팀, 링크 팀의 점수 구하기
        T.solution(0,0);
        System.out.println(min);

    }

    static void solution(int L, int s) {
        // 팀 조합이 완성될 경우
        if(L == n / 2) {
            int startScore = 0;
            int linkScore = 0;
            //i번째 사람과 j번째 사람이 true면 start팀으로 점수 합치기
            for(int i = 0; i < n; i++) {
                for(int j = i + 1; j < n; j++) {
                    if(combi[i] && combi[j]) {
                        startScore += board[i][j];
                        startScore += board[j][i];
                    } else if(!combi[i] && !combi[j]) {
                        linkScore += board[i][j];
                        linkScore += board[j][i];
                    }
                }
            }
            min = Math.min(min, Math.abs(startScore-linkScore));
            //최솟값은 0인데 0이 나오면 바로 끝내버리기
            if(min == 0) {
                System.out.println(0);
                System.exit(0);
            }
        }

        for(int i = s; i < n; i++) {
            // 방문하지 않았다면?
            if(!combi[i]) {
                combi[i] = true;   // 방문으로 변경
                solution(L + 1, i + 1);    // 재귀 호출
                combi[i] = false;  // 재귀가 끝나면 비방문으로 변경
            }
        }
    }
}