[백준 - 14889] 스타트와 링크 - Java

문제 설명

 

14889번: 스타트와 링크

 

접근 방법

해당 문제에서는 전체 n명(짝수)의 사람과 i번 사람 및 j번 사람이 같은 팀에 속했을 때의 능력치가 주어졌을 때 그리고 n명의 사람이 반으로 나누어 팀을 이루었을 때 각 팀의 능력치 차이가 가장 적은 값을 요구하고있습니다.

 

처음 이 문제를 봤을 때 어떤 규칙성을 찾기 보다도 브루트포스 및 백트래킹을 이용해야겠다는 생각을 우선적으로 했습니다. 지금 생각해보면 어리석었지만 저는 각 팀원별 순서를 따지는 경우의 수인 순열을 이용하면서 모든 경우의 수를 따졌었습니다.

 

당연하게도 결과는 시간 초과. 근본적으로 뭐가 잘못됐는지 생각해봤는데, 순열의 경우 팀을 나눈 경우가 중복되는 것이었습니다. 예를 들어 총 4명이 주어졌을 때 1번 사람과, 2번 사람이 팀을 이루고, 3번 사람과 4번 사람이 팀을 이루는 경우는 단 한가지 입니다. 하지만 순열로 이를 접근하면 2번 사람과 1번사람이 팀을 이루고, 4번 사람과 3번 사람이 팀을 이루는 경우가 또 다른 경우의 수로 잡히게 됩니다.

 

결론적으로 불필요한 탐색을 하게 되면서 시간 초과가 났던 것입니다. 그리하여 조합을 통해서 우선적으로 n / 2명의 인원만 선택한 후 이들로 구성된 팀에 대한 능력치의 합을 구하고 나머지 선택되지 않은 사람들이 이루는 팀에 대한 능력치의 합을 구하여 차이를 구하도록 했습니다.

 

 

전체 소스 코드

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

class Main {

    static int result = 1000, n;
    static int[][] abilities;

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

        n = Integer.parseInt(br.readLine());

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

        boolean[] visited = new boolean[n + 1];
        select(visited, 1, 0);

        System.out.println(result);
    }

    private static void select(boolean[] visited, int depth, int count) {
        if (count == n / 2) {
            verify(visited);
            return;
        }

        if (depth == n + 1) {
            return;
        }

        visited[depth] = true;
        select(visited, depth + 1, count + 1);
        visited[depth] = false;
        select(visited, depth + 1, count);
    }

    private static void verify(boolean[] visited) {
        List<Integer> start = new ArrayList<>();
        List<Integer> link = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (visited[i]) {
                start.add(i);
            } else {
                link.add(i);
            }
        }

        int startAbility = 0, linkAbility = 0, half = n / 2;

        int x, y, z, w;
        for (int i = 0; i < half ; i++) {
            for (int j = i + 1; j < half; j++) {
                x = start.get(i);
                y = start.get(j);
                z = link.get(i);
                w = link.get(j);
                startAbility += abilities[x][y] + abilities[y][x];
                linkAbility += abilities[z][w] + abilities[w][z];
            }
        }

        result = Math.min(result, Math.abs(startAbility - linkAbility));
    }
}

 

참고자료

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