[백준 14889번] 자바 스타트와 링크 lv > silver2

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

14889번: 스타트와 링크

참고 > 다른 분들의 제출결과를 비교해보니 시간이 짧은 편에 속해서 뿌듯했습니다!!
            답지보지 않고 풀이해서 더 뿌듯하구요 !! (시간은 오래걸렸지만 ㅎㅎ)

 

문제 설명

예제 입력 1 복사

4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0

예제 출력 1 복사

0

예제 입력 2 복사

6
0 1 2 3 4 5
1 0 2 3 4 5
1 2 0 3 4 5
1 2 3 0 4 5
1 2 3 4 0 5
1 2 3 4 5 0

예제 출력 2 복사

2

예제 입력 3 복사

8
0 5 4 5 4 5 4 5
4 0 5 1 2 3 4 5
9 8 0 1 2 3 1 2
9 9 9 0 9 9 9 9
1 1 1 1 0 1 1 1
8 7 6 5 4 0 3 2
9 1 9 1 9 1 0 9
6 5 4 3 2 1 9 0

예제 출력 3 복사

1

힌트

예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.

 

 

문제 해석

항상 N값은 짝수이고 N/2명씩 두 팀으로 나뉜다.

이 때 두 팀의 능력치의 차이가 최소가 될 때를 출력하면 된다.

ex> 

N = 6명이 주어졌을 때(1, 2, 3, 4, 5, 6)

3명씩 각 팀을 나누는 경우의 수 중 (1, 2, 3) A팀, (4, 5, 6) B팀으로 나뉘었을 때 각 팀의 능력치 계산

A팀의 능력치  = (S[1][2] + S[2][1] +S[1][3] + S[3][1] + S[2][3] + S[3][2])

B팀의 능력치  = (S[4][5] + S[5][4] +S[4][6] + S[6][4] + S[5][6] + S[6][5])

 

* 구현 로직 *

그림 설명:

그림을 보시면 (1,2)A팀, (3, 4) B팀일 때 A팀의 능력치 합과 B팀의 능력치 합은 전체 sum에서 1행의 전체합, 2행의 전체합, 1열의 전체합, 2열의 전체합을 뺀 뒤 중복으로 빠진 A팀의 능력치를 각각 더해주면 됩니다.

그래서 저는 A팀만 고르는 경우만 생각했고 자동으로 B팀의 능력치 합도 행별 합과 열별 합을 이용해서 구했습니다.

 

1. S행렬을 모두 더한 값 sum을 구한다.

2. 행별로 sum을 구해놓고 열별로 sum을 구해놓는다. (전체 sum에서 두 번째 팀의 sum을 구하기 위함)

3. i = 1을 먼저 택한 뒤 첫 번째 팀(A팀)만 고른다 -> 자동으로 두 번째 팀(B팀) 할당되기 때문

4. visit 배열으로 택한 것들은 true로 두고 N/2개가 될 때까지 택한다. 택할 때 첫 번째 팀의 sum은 각 S[i][j] + S[j][i]를 합한다.

코드

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

public class BJ14889 {
    static int N;
    static int[][] S;
    static boolean[] visited;
    static int minDiff = Integer.MAX_VALUE;
    static int sum = 0;
    static int firstTeamSum = 0;
    static int[] rowSum;
    static int[] colSum;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        visited = new boolean[N];
        S = new int[N][N];
        rowSum = new int[N];
        colSum = new int[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            rowSum[i] = 0;
            for (int j = 0; j < N; j++) {
                S[i][j] = Integer.parseInt(st.nextToken());
                sum += S[i][j];
                rowSum[i] += S[i][j];
            }
        }

        for (int i = 0; i < N; i++) {
            colSum[i] = 0;
            for (int j = 0; j < N; j++) {
                colSum[i] += S[j][i];
            }

        }
        visited[0] = true;
        sum -= (rowSum[0] + colSum[0]);
        combination(0,1);
        System.out.println(minDiff);
    }

    public static void combination(int idx, int cnt) {
        if (cnt == N / 2) {
            int secondTeamSum = sum;
            minDiff = (int)Math.min(minDiff, (int)Math.abs(firstTeamSum - secondTeamSum));
            return;
        }

        for (int i = idx; i < N; i++) {
            if (!visited[i]) {
                int tmp = sum;
                visited[i] = true;
                firstTeamSum += (S[i][idx] + S[idx][i]);
                sum -= (rowSum[i] + colSum[i]);
                sum += (S[i][idx] + S[idx][i]);
                combination(i, cnt + 1);
                firstTeamSum -= (S[i][idx] + S[idx][i]);
                sum = tmp;
                visited[i] = false;
            }
        }
    }
}-