스타트와 링크 14899번 문제

이 문제는 브루트포스 (완전탐색)으로 해결 할 수 있다.

N= 6 으로 입력 된 경우 해당 3개씩 나눠서 조합을 구해보면 된다.

0 1 2 3 4 5

1 0 2 3 4 5

1 2 0 3 4 5

1 2 3 0 4 5

1 2 3 4 0 5

1 2 3 4 5 0

(1,3,6) ( 2,4,5)

a[1][3] = 2

a[1][6] = 5

a[3][6] = 5

a[3][1] = 1

a[6][1] = 1

a[6][3] = 3

=== 17=====

a[2][4] = 3

a[2][5] = 4

a[4][5] = 4

a[4][2] = 2

a[5][2] = 2

a[5][4] = 4

===19=======

이런경우 최소값은 2가 된다. 단순 dfs로 적절히 가지수가 나오게

 for(int i=index; i<=n; i++) {

    if(!check[i]) {

check[i] = true;

solve(i+1,depth+1);

check[i] = false;    

     }

}

이런식으로 백트래킹 처리를 해주었다.

전체코드   

import java.util.*;
public class Main {
     static int arr[][];
     static int n;
     static boolean check[];
     static int total_min = Integer.MAX_VALUE;
     public static void main(String[] args) {
         // TODO Auto-generated method stub
         Scanner sc = new Scanner(System.in);
         n = sc.nextInt();
         arr = new int [n+1][n+1];
         check = new boolean[n+1];
         for(int i=1; i<=n; i++) {
             for(int k=1; k<=n; k++) {
                 arr[i][k] = sc.nextInt();
             }
         }
         solve(1,0);
         System.out.println(total_min);
     }
     public static int get_a_min() {
         int mins = 0;
         for(int i=1; i<=n; i++) {
             if(!check[i])
                 continue;
             for(int k=1;k<=n; k++) {
                 if(i==k)
                     continue;
                 if(check[i] && check[k]) {
                     mins+= arr[i][k];
                 }
             }
         }
         return mins;
     }
     public static int get_b_min() {
         int mins = 0;
         for(int i=1; i<=n; i++) {
             if(check[i])
                 continue;
             for(int k=1;k<=n; k++) {
                 if(i==k)
                     continue;
                 if(!check[i] && !check[k]) {
                     mins+= arr[i][k];
                 }
             }
         }
         return mins;
     }
     public static void solve(int index, int depth) {
         if(depth == n/2) {
             // 최소값 구해주기
             total_min = Math.min(total_min, Math.abs(get_a_min()-get_b_min()));
         }
         for(int i=index; i<=n; i++) {
             if(!check[i]) {
                 check[i] = true;
                 solve(i+1,depth+1);
                 check[i] = false;
             }
         }
     }
}