BOJ 14889 - 스타트와 링크

14889번: 스타트와 링크

 

 

 

 

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

 

 

 

1. 아이디어

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

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

 

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

 

겨우 생각해낸 방법이지만 코드가 좀 더럽다.. 분명 더 최적화 할 방법이 있을 거 같은데 아직은 떠오르지가 않는다 ㅠ

 

2. 시간복잡도

N의 최댓값은 20이고 조합의 시간복잡도는 O(2^N)라서 2^20이다.

팀 능력치를 계산할 때에도 이중 for문으로 전부 더해주면 되는거라 O(N^2)라서 20^2이다.

 

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

 

3. 구현

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());
            }
        }

    }
}