백준 14889 풀이

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

2차원 배열 전체 탐색하여 원하는 결과를 찾는 문제였다.

전체 n명의 사람을 2팀으로 나누어 만들 수 있는 경우를 구하여 두 팀의 능력치의 합의 최소를 구하면 되는 문제이다.

문제를 처음 보고 든 생각은 앞서 풀었던 N과M 문제에서 응용을 하면되겠다였다.

실제로 그렇게 구현을 하여 문제에 제시된 예제에 대해서는 문제없이 통과가 되었다. 하지만 제출만 하면 발생하는 "시간초과"...

다시 코드를 살펴보고 나오는 경우의 수에 대해서 분석한 결과 이미 만들어진 팀이 나중에 다시 한번 더 만들어지는 등 중복된 결과가 존재한다는 사실을 알았고 이 부분을 수정해서 다시 제출했다.

결과는 통과!!!

앞선 코드를 수정하는데 있어 주안점은 '현재 선택한 선수 이전의 번호를 가진 선수는 선발하지 못하게 한다'는 것 같다.

즉, 현재 선택한 선수가 3번이면 1번 선수는 선택하지 못하게 함으로서 중복을 방지했다.

import java.io.*;

public class Main {
    static boolean[] visited;
    static int[] p;
    static int[] ap;
    static int[][] arr;
    static int min = 101;

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String num = br.readLine();
        int n = Integer.parseInt(num);
        arr = new int[n][n];
        visited = new boolean[n];
        p = new int[n / 2];
        ap = new int[n / 2];

        for (int i = 0; i < n; i++) {
            visited[i] = false;
            String line = br.readLine();
            String[] lines = line.split(" ");
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(lines[j]);
            }
        }
        dfs(0, 0,n / 2, n);
        System.out.println(min);
        //bw.write(Integer.toString(min));
        br.close();
        bw.close();
    }

    private static void dfs(int cnt,int pos, int m, int n) {
        if (cnt == m) {
            int tmp = 0;
            for (int i = 0; i < n; i++) {
                if (!visited[i]) {
                    ap[tmp] = i;
                    tmp++;
                }
            }
            int start = 0;
            int link = 0;
            for (int i = 0; i < m-1; i++) {
                for (int j = i + 1; j < m; j++) {
                    int x = p[i];
                    int y = p[j];
                    //System.out.println("start team: " + x + ", " + y);
                    start += arr[x][y] + arr[y][x];
                    int xx = ap[i];
                    int yy = ap[j];
                    //System.out.println("link team: " + xx + ", " + yy);
                    link += arr[xx][yy] + arr[yy][xx];
                }
            }
            //System.out.println(start);
            //System.out.println(link);
            int div = Math.abs(start-link);
            //System.out.println("div: "+div);
            if(div<min){
                min = div;
            }
            //System.out.println("----------------------");
            return;
        }
        for (int i = pos; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                p[cnt] = i;
                dfs(cnt + 1,i, m, n);
                visited[i] = false;
            }
        }
    }
}