백준/14889 스타트와 링크 / 조합 = dfs + 백트래킹

스타트와 링크 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

72451

35877

21057

46.362%

문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

i\j12341234

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

예를 들어, 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, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

예제 입력 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

---

풀이

/**
 * start팀과 link팀이 될 수 있는 모든 경우를 구해야한다.
 * 어떻게 구할까 생각했다. int[] 로 모든 사람들 저장하고 , 한명씩 뽑고, 안뽑고를 진행할까?
 * 결국 조합이므로 조합은 뽑고 안뽑고를 진행할때 필요한 boolean[] 방문배열로 뽑은 결과를 알 수 있으므로 뽑힌사람은  start팀 , 안뽑힌사람은 link팀으로한다.
 * 조합을 돌리며 start팀의 능력치와 link팀의 능력치를 구하고 차이를 구하고 min 값을 구한다.
 */

이러한 생각으로 풀이

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    /**
     * start팀과 link팀이 될 수 있는 모든 경우를 구해야한다.
     * 어떻게 구할까 생각했다. int[] 로 모든 사람들 저장하고 , 한명씩 뽑고, 안뽑고를 진행할까?
     * 결국 조합이므로 조합은 뽑고 안뽑고를 진행할때 필요한 boolean[] 방문배열로 뽑은 결과를 알 수 있으므로 뽑힌사람은  start팀 , 안뽑힌사람은 link팀으로한다.
     * 조합을 돌리며 start팀의 능력치와 link팀의 능력치를 구하고 차이를 구하고 min 값을 구한다.
     */

    static int n;
    static int[][] power; //능력치
    static boolean[] visited; // true인 애들이 start팀 false인 애들이 link팀
    static int min= Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {

        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        n = Integer.parseInt(br.readLine());
        power = new int[n][n];
        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                power[i][j] = Integer.parseInt(input[j]);
            }
        }
        visited = new boolean[n];
    }

    static void solve() throws IOException {
        combination(n,n/2,0,visited);
        bw.write(min+"");
    }

    static void combination(int n ,int r, int start ,boolean[] visited) {
        if (r == 0) {
            calculateTeamPower(visited);
            return;
        }
        for (int i = start; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                combination(n, r - 1, i + 1, visited);
                visited[i] = false;
            }
        }
    }

    static void calculateTeamPower(boolean[] visited) { //각 팀의 능력치를 계산하고 차이도 계산한 후 최소값인지 체크하는 메소드
        int startTeamPower=0;
        int linkTeamPower=0;
        for (int i = 0; i < visited.length; i++) {  // [0][0] ~ [n-1][n-1]의 모든경우를 체크한다, 한사람씩 어디에 속해있는지 , 어떤사람과 팀인지 체크하여
            for (int j = 0; j < visited.length; j++) { // [i][j] [j][i] 의 값을 능력치로 더해준다.
                if (visited[i] && visited[j]) { //i번째 선수가 start팀일때, j번째 선수도 start 팀이라면? 능력치를 더해준다.
                    startTeamPower += power[i][j];
                } else if (!visited[i] && !visited[j]) { //혹은 둘다 link팀이라면
                    linkTeamPower += power[i][j];  // link팀 능력치를 올려준다.
                }
            }
        }
        // [i][j]는 더할때 왜 [j][i]는 안더해주나 -> 어차피 반복문 돌면서 [j][i]도 값이 들어가게 되어있다.

        int gap = Math.abs(startTeamPower - linkTeamPower);
        min = Math.min(min, gap);
    }

}