[Java] 백준 스타트와 링크

1. 문제분석

 

스타트팀과 링크팀을 나누어서 각 팀의 능력치를 구하고 팀 전체 능력의 차이가 최소인 점수를 구하는 문제다.

위에서 이미 답을 준 셈이다. 1번과 2번이 팀이고 3번과 4번이 팀이라고 한다.

그 때, {1,2}, {2,1}과 {3,4}, {4,3}, 서로를 더해 빼면 되는 것이다. 위에서 나온 팀을 순열로 구한 것이다.

 

반면 팀은 어떻게 구할까? 여기서 팁은 조합이다.

1번과 2번이 팀인 경우 답을 구했다. 그렇다면 2번과 1번일때 또 구해야할 필요가 있을까?

즉, 조합을 구해서 팀을 꾸리고 능력치를 순열로 구하는 문제다. (팀 : n C n/2, 능력치: n/2 P 2)

2. 구현

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

public class Main {

    static int[][] status;
    static int size;
    static ArrayList<int[]> list = new ArrayList<>();
    static int team1 = 0;
    static int team2 = 0;
    static int result = Integer.MAX_VALUE;

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

        status = new int[size][size];

        for (int i = 0; i < size; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < size; j++) {
                status[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //사람들의 집합
        int[] people = new int[size];
        for (int i = 0; i < size; i++) {
            people[i] = i + 1;
        }
        //조합 방문여부
        boolean[] visited = new boolean[size];
        comb(people, visited, 0, size, size / 2);

        for (int i = 0; i < list.size() / 2; i++) {
            int[] output = new int[size / 2];
            //first team
            perm(list.get(i), output, visited, 0, size / 2, 2, true);

            //second team
            perm(list.get(list.size() - (i + 1)), output, visited, 0, size / 2, 2, false);
            result = Math.min(result, Math.abs(team1 - team2));
            team2 = 0; team1 = 0;
        }
        System.out.println(result);
    }

    static void comb(int[] people, boolean[] visited, int start, int n, int r) {
        if (r == 0) {
            //perm -> calc
            int[] arr = new int[size / 2];
            int pos = 0;
            for (int i = 0; i < n; i++) {
                if (visited[i]) {
                    arr[pos++] = people[i];
                }
            }
            list.add(arr);
        } else {
            for (int i = start; i < n; i++) {
                visited[i] = true;
                comb(people, visited, i + 1, n, r - 1);
                visited[i] = false;
            }
        }
    }

    static void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r, boolean check) {
        if (depth == r) {
            int x = output[0] - 1, y = output[1] - 1;
            if(check) {
                team1 += status[x][y];
            }
            else {
                team2 += status[x][y];
            }
        } else {
            for (int i = 0; i < n; i++) {
                if (!visited[i]) {
                    visited[i] = true;
                    output[depth] = arr[i];
                    perm(arr, output, visited, depth + 1, n, r, check);
                    output[depth] = 0;
                    visited[i] = false;
                }
            }
        }
    }
}

순열과 조합, 둘 다 백트래킹으로 구했다.

팀원은 반드시 짝수라고 하니 팀 구성은 항상 (n C n/2) 가 된다.

구한 팀원의 조합은 list에 넣어둔다. 필자는 start, 즉, 첫 지점을 0으로 시작했기 때문에 맨처음과 끝이 서로 대립된다.

(여기서 대립은 1,2 -> 3,4를 뜻한다.)

 

구한 팀원을 순열로 능력치를 구하고 절댓값으로 차이를 구했다.

그 후, 차이의 최솟값을 출력해주면 된다.

3. 마무리

순열은 아직 정리를 안했지만 조합을 정리하고 풀어본 문제다.

확실히 조합에 대해 알고 풀어보니 오류 없이 한번에 통과할 수 있었다.

조합과 순열이 이해가 안된다면 이 포스팅을 보고 구해보자.

2022.08.27 - [문법/Java] - [Java] 조합

[Java] 조합

2022.09.21 - [문법/Java] - [Java] 순열

[Java] 순열