BOJ 14889 - 스타트와 링크

14889번: 스타트와 링크 (acmicpc.net)

 

능력치의 차이를 최소화.

분할된 팀의 능력치를 구할 수 있어야 한다.

우선 N 명을 N/2 명 씩 두 팀으로 나눠야 한다.

그 후 각 팀의 점수를 계산해서 차이를 구한 다음 갱신을 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {

    static FastReader scan = new FastReader();
    static int N;
    static int[][] status;
    static int minGap = Integer.MAX_VALUE;

    static void input() {
        N = scan.nextInt();
        status = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                status[i][j] = scan.nextInt();
            }
        }
    }

    static void recFunc(int depth, int[] team, boolean[] visited) {
        if (depth >= N/2) {
            Set<Integer> teamA = Arrays.stream(team).boxed().collect(Collectors.toSet());
            Set<Integer> teamB = IntStream.range(0, N)
                    .boxed()
                    .collect(Collectors.toSet());
            teamB.removeAll(teamA);
            calculate(teamA, teamB);
            return;
        }

        for (int i = depth == 0 ? 0 : team[depth - 1]; i < N; i++) {
            if (visited[i]) continue;
            team[depth] = i;
            visited[i] = true;
            recFunc(depth + 1, team, visited);
            team[depth] = 0;
            visited[i] = false;
        }
    }

    static void calculate(Set<Integer> teamA, Set<Integer> teamB) {
        int teamAScore = calculateTeamScore(teamA);
        int teamBScore = calculateTeamScore(teamB);
        minGap = Math.min(minGap, Math.abs(teamAScore - teamBScore));
    }

    static int calculateTeamScore(Set<Integer> team) {
        int score = 0;

        for (int user1 : team) {
            for (int user2 : team) {
                if (user1 == user2) continue;
                score += status[user1][user2];
            }
        }
        return score;
    }

    public static void main(String[] args) {
        input();
        recFunc(0, new int[N/2], new boolean[N]);
        System.out.println(minGap);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

그런데 이제 보니까 teamA와 teamB의 Set은 필요가 없다. 이미 visited에서 방문한 사람들을 체크하고 있기 때문에 해당 배열이 true이면 A팀 false면 B팀으로 처리하면 된다. 그냥 팀을 나눠야 한다는 생각에 쓸모없는 시간과 공간을 낭비했다.

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

public class Main {

    static FastReader scan = new FastReader();
    static int N;
    static int[][] status;
    static int minGap = Integer.MAX_VALUE;

    static void input() {
        N = scan.nextInt();
        status = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                status[i][j] = scan.nextInt();
            }
        }
    }

    static void recFunc(int depth, int[] team, boolean[] visited) {
        if (depth >= N/2) {
            int scoreGap = calculateTeamScoreGap(visited);
            minGap = Math.min(minGap, scoreGap);
            return;
        }

        for (int i = depth == 0 ? 0 : team[depth - 1]; i < N; i++) {
            if (visited[i]) continue;
            team[depth] = i;
            visited[i] = true;
            recFunc(depth + 1, team, visited);
            team[depth] = 0;
            visited[i] = false;
        }
    }

    static int calculateTeamScoreGap(boolean[] visited) {
        int score = 0;

        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (visited[i] && visited[j]) {
                    score += status[i][j] + status[j][i];
                } else if (!visited[i] && !visited[j]) {
                    score -= status[i][j] + status[j][i];
                }
            }
        }
        return Math.abs(score);
    }

    public static void main(String[] args) {
        input();
        recFunc(0, new int[N/2], new boolean[N]);
        System.out.println(minGap);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}