[SWEA] 4012. 요리사

조합을 사용하는 문제이다.

백트래킹을 사용하는 comb함수를 구현하여 N개중에서 N/2개를 뽑는 조합의 경우를 구하고, 그 경우 마다 check함수를 적용시켜 서로 다른 두 집합의 시너지 합이 최소가 되는 경우를 찾았다. check함수에서는 visit배열을 기준으로 방문의 유무를 이용하여 두개의 그룹으로 나누었다. 그리고 이 check함수에서도 2개씩 뽑아내야 하는 조합이 있는데 이것은 단순 이중for문으로 구현하였다. 

문제를 이해하는데 꽤 많은 시간이 걸려서 다른 블로그를 참고하였다. 문제의 의도를 파악하는 연습이 필요한 것 같다.

package swea;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
 
public class Solution_4012_요리사 {
    
    static int N;
    static int[][] arr;
    
    static int[] data;
    static int[] result;
    static boolean[] visit;
    
    static int answer;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int T=Integer.parseInt(br.readLine());
        
        for(int tc=1;tc<=T;tc++) {
            N=Integer.parseInt(br.readLine());
            arr=new int[N][N];
            
            for(int i=0;i<N;i++) {
                st=new StringTokenizer(br.readLine());
                for(int j=0;j<N;j++)
                    arr[i][j]=Integer.parseInt(st.nextToken());
            }
            
            data=new int[N];
            for(int i=0;i<N;i++)
                data[i]=i;
            result=new int[N/2];
            visit=new boolean[N];
            answer=Integer.MAX_VALUE;
            comb(0,0);
            
            System.out.println("#"+tc+" "+answer);
        }
    }
    
    static void comb(int start, int depth) {
        if(N/2==depth) {
//            System.out.println(Arrays.toString(result));
//            System.out.println(Arrays.toString(visit));
            checkMinimum();
            
            return;
        }
        for(int i=start;i<N;i++) {
            if(visit[i]==false) {
                visit[i]=true;
                result[depth]=data[i];
                comb(i,depth+1);
                visit[i]=false;
            }
        }
    }
    
    static void checkMinimum() {
        List<Integer> forA = new ArrayList<>();
        List<Integer> forB = new ArrayList<>();
        
        for(int i=0;i<N;i++) {
            if(visit[i]==true)
                forA.add(i);
            else
                forB.add(i);
        }
        
        int totalA=0;
        int totalB=0;
        
        for(int i=0;i<forA.size()-1;i++) {
            for(int j=i;j<forB.size();j++) {
                totalA+=arr[forA.get(i)][forA.get(j)];
                totalA+=arr[forA.get(j)][forA.get(i)];
                totalB+=arr[forB.get(i)][forB.get(j)];
                totalB+=arr[forB.get(j)][forB.get(i)];
            }
        }
        
        answer=Math.min(answer, Math.abs(totalA-totalB));
    }
}