kingsubin

import java.io.*;
import java.util.*;
 
public class boj_14889 {
    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 index) {
        if (index == N) {
            if (team1.size() != N/2) return;
            if (team2.size() != N/2) return;
 
            int diff = calculate(team1, team2);
            min = Math.min(min, diff);
        }
 
        if (team1.size() > N/2) return;
        if (team2.size() > N/2) return;
 
        team1.add(index);
        func(index+1);
        team1.remove(team1.size()-1);
 
        team2.add(index);
        func(index+1);
        team2.remove(team2.size()-1);
    }
 
    private static int calculate(ArrayList<Integer> team1, ArrayList<Integer> team2) {
        int t1 = 0;
        int t2 = 0;
        for (int i = 0; i < N/2; i++) {
            for (int j = 0; j < N/2; j++) {
                if (i == j) continue;
                t1 += map[team1.get(i)][team1.get(j)];
                t2 += map[team2.get(i)][team2.get(j)];
            }
        }
 
        return Math.abs(t1 - t2);
    }
}
 

 

- 재귀, 브루트포스

 

- 현재의 선수를 team1에 넣을지 team2에 넣을지 라고 생각 

- N 제한이 20 까지니까 2^20이라 시간제한 충분

- 백트래킹하듯이 team에 넣고 다음 선수 찾기, team에서 빼기 이런식으로 func 계속 호출

- 모든 선수를 팀에 다 배정 완료되었고 인원수도 맞으면 calculate 이후에 min 갱신

 

 

---

    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());
            }
        }
 
        for (int i = 0; i < (1 << N); i++) {
            int cnt = 0;
            for (int j = 0; j < N; j++) {
                if ((i & (1 << j)) == 0) {
                    cnt += 1;
                }
            }
            if (cnt != N / 2) continue;
 
            ArrayList<Integer> team1 = new ArrayList<>();
            ArrayList<Integer> team2 = new ArrayList<>();
            for (int j = 0; j < N; j++) {
                if ((i & (1 << j)) == 0) {
                    team1.add(j);
                } else {
                    team2.add(j);
                }
            }
 
            int calculate = calculate(team1, team2);
            min = Math.min(min, calculate);
        }
        System.out.println(min);
    }

 

- 20.12.09 비트마스크 풀이 추가

 

 

 

 

---

www.acmicpc.net/problem/14889