[백준] 14889번 : 스타트와 링크 - 자바(JAVA)

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

14889번: 스타트와 링크

 

문제 해석

축구를 하기 위해 모인 사람은 N명이고 N은 짝수입니다.

N/2명으로 두 팀을 나누려고 합니다.

 

N=4일때 다음과 같이 시너지를 가집니다.

두 팀의 능력치의 차이를 최소로 하려고 합니다.

 

문제 풀이전 설계

S(i,j)는 1~100사이의 수 입니다.

N은 4이상 20이하의 짝수입니다.

 

우선 두 그룹으로 나누는 작업을 수행합니다.

(1,2) / (3,4)

(1,3) / (2,4)

(1,4) / (2,3)

 

이때 순서는 의미가 없기 때문에 조합을 통하여 그룹나누는 작업을 수행합니다.

 

그룹이 나누어지면 각 그룹의 능력치를 합산하는 작업을 합니다.

 

각 그룹의 능력치의 차이를 구하고 최솟값을 갱신하는 작업을 합니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main_14889_스타트와링크 {

    static int result = Integer.MAX_VALUE;
    static int N;
    static int[][] ability;
    static Set<Integer> groupsA = new HashSet<>();
    static Set<Integer> groupsB = new HashSet<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());


        ability = new int[N + 1][N + 1];

        StringTokenizer st = null;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                ability[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        findMinAbilityGap(0, 1);
        System.out.println(result);
    }

    private static void findMinAbilityGap(int count, int start) {
        if (count == N / 2) {
            for (int i = 1; i <= N; i++) {
                if (!groupsA.contains(i)) {
                    groupsB.add(i);
                }
            }

            //그룹 A와 그룹 B가 만들어짐
            getMinAbilityGapByGroup();

            groupsB.clear();
            return;
        }

        for (int i = start; i <= N; i++) {
            groupsA.add(i);
            findMinAbilityGap(count + 1, i + 1);
            groupsA.remove(i);
        }

    }

    private static void getMinAbilityGapByGroup() {

        //GroupA
        int[] groupA = groupsA.stream()
                              .mapToInt(e -> e)
                              .toArray();
        int abilitySumA = 0;
        int size = groupA.length;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                abilitySumA += ability[groupA[i]][groupA[j]];
            }
        }

        //GroupB
        int[] groupB = groupsB.stream()
                              .mapToInt(e -> e)
                              .toArray();
        int abilitySumB = 0;
        size = groupB.length;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                abilitySumB += ability[groupB[i]][groupB[j]];
            }
        }

        result = Math.min(Math.abs(abilitySumA - abilitySumB), result);

    }
}