[BOJ] 14889 스타트와 링크 - Java

문제

https://www.acmicpc.net/problem/14889

14888번: 연산자 끼워넣기

 

---

풀이

• N이 주어졌을 때 N/2명으로 두 팀을 나눈다
• 각 팀 간의 능력치 차이가 최소가 되는 경우를 구한다

---

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main{
    static int n, min;
    static int[][] team;
    static boolean[] used;
    static int[] teamA;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        team = new int[n][n];
        used = new boolean[n];
        min = Integer.MAX_VALUE;
        teamA = new int[n/2];

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                team[i][j] = sc.nextInt();
            }
        }

        Comb(0, 0);
        System.out.println(min);

    }

    private static void Comb(int cnt, int start) {
        if(cnt == n/2){
            int[] teamB = new int[n/2];
            int idx = 0;
            for(int i=0; i<n; i++){
                if(!used[i]){
                    teamB[idx++] = i;
                }
            }

            int a = 0, b = 0;
            for(int i=0; i<n/2; i++){
                for(int j=0; j<n/2; j++){
                    a += team[teamA[i]][teamA[j]];
                    b += team[teamB[i]][teamB[j]];
                }
            }
            min= Math.min(min, Math.abs(a-b));

            return;
        }

        for(int i=start; i<n; i++){
            teamA[cnt] = i;
            used[i] = true;
            Comb(cnt+1, i+1);
            used[i] = false;
        }
    }
}

• 팀원이 중복되지 않고, 두 팀을 나눠야하므로 조합 사용
• 각각의 팀원 별로 주어진 능력치를 합산하여 팀A와 팀B의 능력치의 차와 최소 값을 비교하며 최소 값 갱신