boj 14889 스타트와 링크

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

조합으로 N/2개를 뽑은 후에 뽑은 것들의 조합의 능력치를 N^2으로 각각 계산해줍니다.

그 다음 abs(a-b)의 차이의 최소를 구해 출력해주시면 됩니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static boolean pick[] = new boolean[21];
    static int list[][] = new int[21][21];
    static int N, ans = Integer.MAX_VALUE;
 
    static void func(int idx, int cnt) {
        if (cnt == N / 2) {
            int a = 0;
            int b = 0;
            for (int i = 0; i < N; i++) {
                for (int j = i + 1; j < N; j++) {
                    if (pick[i] == pick[j]) {
                        if (pick[i])
                            a += (list[i][j] + list[j][i]);
                        else
                            b += (list[i][j] + list[j][i]);
                    }
                }
            }
 
            ans = Math.min(ans, Math.abs(a - b));
            return;
        }
 
        for (int i = idx; i < N; i++) {
            pick[i] = true;
            func(i + 1, cnt + 1);
            pick[i] = false;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                list[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(0, 0);
        System.out.println(ans);
    }
}