[SW Expert Academy] 요리사

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH&categoryId=AWIeUtVakTMDFAVH&categoryType=CODE&problemTitle=sw&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

package SW.알고리즘;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 요리사 {
    static int map[][];
    static int N;
    public static void main(String[] args) throws NumberFormatException, IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int T = Integer.parseInt(br.readLine());
            for(int test_case = 1; test_case<=T; test_case++) {
                N = Integer.parseInt(br.readLine());
                map = new int[N][N];
                for(int i=0; i<N; i++) {
                    StringTokenizer st = new StringTokenizer(br.readLine());
                    for(int j=0; j<N; j++) {
                        map[i][j] = Integer.parseInt(st.nextToken());
                    }
                }

                min = Integer.MAX_VALUE;
                check = new boolean[N];
                combination(0, 0);
                System.out.println("#"+test_case+ " "+ min);


            }
    }

    static int min;
    static boolean check[];
    static int numbers[];
    private static void combination(int k, int idx) {
        if(idx == N/2) {
            int a[] = new int[N/2];
            int b[] = new int[N/2];

            int aIdx = 0;
            int bIdx = 0;
            for(int i=0; i<N; i++) {
                if(check[i]== true) {
                    a[aIdx++] = i;
                }
                else {
                    b[bIdx++] = i;
                }
            }

            int sumA = 0;
            int sumB = 0;
            for(int i=0; i<N/2; i++) {
                for(int j=0; j<N/2; j++) {
                    sumA += map[a[i]][a[j]];
                    sumB += map[b[i]][b[j]];
                }
            }
            min = Math.min(Math.abs(sumA-sumB), min);


        }
        for(int i=k; i<N; i++) {
            if(check[i] == false) {
                check[i] = true;
                combination(i+1, idx+1);
                check[i] = false;
            }
        }
    }
}

소요시간 : 30분

요리사는 음식을 N/2개 골라서 조합해서 두 분류로 나누고 최솟값을 구하는 문제입니다.

쉬운 문제였습니다!!