[백준 14889] 스타트와 링크

[jusung-c]

문제

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

---

아이디어

모든 N은 짝수이고 N/2명씩 팀을 짜니까

N개의 자연수에서 중복을 허용하지 않고 N/2개를 순서와 상관없이 나열하는 조합 문제이다.

팀 능력치를 stats[][]을 이용해 저장해두고 팀이 될 수 있는 모든 경우의 조합을 구해서 스타트팀 능력치를 계산하고 팀에 속하지 않은 팀(링크팀) 능력치도 계산해서 차이를 구한 후 min값을 갱신한다.

팀 능력치를 구할 때에는 각 팀별로 이중for으로 전부 stats[][]을 이용해 더해주었다. 겨우 생각해낸 방법이지만 짜고나니 분명 이것보단 나은 방법이 있을 것 같다..

---

시간복잡도

N의 최댓값은 20이고 조합의 시간복잡도는 O(2^N)라서 2²⁰이다.
팀 능력치를 계산할 때에도 이중 for문으로 전부 더해주면 되는거라 O(N²)라서 20²이다.

따라서 2초 안에 풀이가 가능하다.

---

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M;
    static int[][] stats;
    static int[] start_team, visit;
    static int min;

    public static void main(String[] args) throws IOException {
        init();

        rec_func(1, 0);

        bw.write(min + " ");
        bw.close();
    }

    private static void rec_func(int k, int prev) throws IOException {
        if (k == M+1) {
            // 팀 점수 계산 후 최솟값 갱신
            calculate();
            /*for (int i = 1; i <= M; i++) {
                bw.write(start_team[i]+" ");
            }
            bw.write("\n");*/
        } else {
            for (int i = prev + 1; i <= N; i++) {
                if(visit[i] == 1) continue;

                start_team[k] = i;
                visit[i] = 1;

                rec_func(k + 1, i);

                start_team[k] = 0;
                visit[i] = 0;
            }
        }
    }

    private static void calculate() throws IOException {
        int start_score = 0;
        int link_score = 0;

        // link 팀 멤버
        int[] link_team = new int[M + 1];
        int index = 1;

        for (int i = 1; i <= N; i++) {
            if (visit[i] == 0) {
                link_team[index] = i;
                index++;
            }
        }

        // 팀 점수 계산
        for (int i = 1; i <= M; i++) {
            for (int j = i + 1; j <= M; j++) {
                int a = start_team[i];
                int b = start_team[j];
                int c = link_team[i];
                int d = link_team[j];

//                bw.write(a+"/"+b+"/"+c+"/"+d+"/"+"\n");

                start_score += stats[a][b];
                start_score += stats[b][a];

                link_score += stats[c][d];
                link_score += stats[d][c];
            }
        }

//        bw.write(start_score+"/"+link_score+"\n");

        int result = Math.abs(start_score - link_score);

        min = Math.min(result, min);
    }

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        M = N/2;

        stats = new int[N + 1][N + 1];
        visit = new int[N + 1];
        start_team = new int[M + 1];
        min = Integer.MAX_VALUE;

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

    }
}

---

맞기는 맞았는데 뭔가 더럽다.. 좀 더 최적화할 수 있는 방법이 있을 거 같은데 일단 넘어가..

[ghdcksgml1]

ㄷㄷ 구현 완전 깔끔한데?? 굳굳 잘했네~