BOJ) 스타트와 링크

스타트와 링크

14889번: 스타트와 링크

풀이

 

주어진 짝수 인원(4~20)이 축구 경기를 하는데, n/2 : n/2 경기를 해야한다.

이 때, 실력차이가 가장 적게나는 경우를 찾는 문제다.

결국, 모든 경우의 수를 다 파악해야하는 Brute-force 문제였다.

n이 20이나 되지만, DFS를 선택했다.

왜냐하면, N=20인 경우, 10 : 10 경기를 하기 때문에, 결론적으로는 2^20까지 가지 않기 때문이다.

중간에 한쪽 팀이 N의 절반이 넘어가는 경우를 가지치기만 해준다면 가능하다고 생각했다.

 

dfs를 통해 0~N-1까지 left팀과 right팀에 선수 번호를 넣어주었다.

마지막 선수까지 배치가 끝났을 때, 주어진 능력치를 더해서 left와 right의 SUM을 각각 구해주었다.

능력치의 차이는 기준이 없기 때문에, Math.abs()를 이용해서 절대 값을 구해주었다.

그리고, answer와 min 값을 구해주면서 답을 구했다.

 

이 문제도, 가지치기만 잘 설정한다면 크게 어렵지 않은 문제였다.

 

코드

 

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

public class StartLink_14889 {
    static int answer;
    static int[][] abilities;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        abilities = new int[n][n];

        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++) {
                abilities[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        solution(n);
    }

    private static void solution(int n) {
        answer =Integer.MAX_VALUE;
        dfs(n,0,n/2, new ArrayList<>(), new ArrayList<>());
        System.out.println(answer);
    }

    private static void dfs(int n, int idx, int half, ArrayList<Integer> left, ArrayList<Integer> right) {
        if(left.size() > half || right.size() > half) {
            return;
        }

        if(idx == n) {
            int leftSum =0, rightSum =0;
            for(int i=0; i<half; i++) {
                for(int j=i; j<half; j++) {
                    leftSum += abilities[left.get(i)][left.get(j)] + abilities[left.get(j)][left.get(i)];
                    rightSum += abilities[right.get(i)][right.get(j)] + abilities[right.get(j)][right.get(i)];
                }
            }
            answer = Math.min(answer,Math.abs(leftSum-rightSum));
            return;
        }

        left.add(idx);
        dfs(n, idx+1, half, left, right);
        left.remove(left.size()-1);
        right.add(idx);
        dfs(n, idx+1, half, left, right);
        right.remove(right.size()-1);
    }
}