kingsubin

import java.io.*;
import java.util.*;
 
public class boj_15661 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N;
    static int min = Integer.MAX_VALUE;
    static int[][] map;
    static ArrayList<Integer> team1 = new ArrayList<>();
    static ArrayList<Integer> team2 = new ArrayList<>();
 
    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        func(0);
        System.out.println(min);
    }
 
    static void func(int k) {
        if (k == N) {
            if (team1.size() > 0 && team2.size() > 0) {
                int t1 = 0;
                int t2 = 0;
 
                t1 = getT(t1, team1);
                t2 = getT(t2, team2);
 
                int diff = Math.abs(t1 - t2);
                min = Math.min(min, diff);
            }
            return;
        }
 
        team1.add(k);
        func(k+1);
        team1.remove(team1.size()-1);
 
        team2.add(k);
        func(k+1);
        team2.remove(team2.size()-1);
    }
 
    static int getT(int t, ArrayList<Integer> team) {
        for (int i = 0; i < team.size(); i++) {
            for (int j = 0; j < team.size(); j++) {
                if (i == j) continue;
                t += map[team.get(i)][team.get(j)];
            }
        }
        return t;
    }
}
 

 

- 브루트포스, 재귀 

- www.acmicpc.net/problem/14889 문제와 유사함

 

- N번 까지 team1 에 추가할지 team2 에 추가할지 선택

- 모든 경우의 수에 대해 차이 구하고 min 갱신

 

 

 

 

---

www.acmicpc.net/problem/15661