[SW Expert] 4012. [모의 SW 역량테스트] 요리사

생각

주어진 식재료를 반절씩 나누어 A 음식과 B 음식을 만든다.
음식을 만들 때 몇 번째 재료를 사용하였나에 따라서 재료에 따른 시너지 효과가 달라진다.
예를들어 아래와 같은 시너지가 주어졌을 때,

1과 2로 A 음식을 만들면 5 + 4의 시너지인 9가 된다.
B음식은 3과 4로 3 + 3 = 6의 시너지가 되어
음식의 차이는 시너지의 차이인 3이된다. 이 차이가 최소가 되는 값을 찾아라.

처음 생각

주어진 재료 개수에서 n/2개를 선택해서 A음식을 만들고 선택되지 않은 재료들로 B음식을 만들어 주기위해 방문 배열을 만들고 DFS를 이용하여 부분 집합을 만들어 주었다.

방안

1) 입력에 개행이 많이 섞여서 주어지기 때문에 BufferedReader를 사용하지 않고, Scanner를 사용해서 입력을 받았다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

import java.io.IOException; import java.util.Scanner;   class Solution {     static int n;     static int[][] arr;     public static void main(String[] args) throws IOException{         Scanner sc = new Scanner(System.in);         int tc = sc.nextInt();         StringBuilder sb = new StringBuilder();         for(int i=1;i<=tc;i++) {             n = sc.nextInt();             arr = new int[n][n];             for(int j=0;j<n;j++) {                 for(int k=0;k<n;k++)                     arr[j][k] = sc.nextInt();             }             visited = new boolean[n];             result = Integer.MAX_VALUE;             solve(0,0);             sb.append("#"+i+" "+result+"\n");         }         System.out.print(sb);     }          static boolean visited[];     static int result;     private static void solve(int idx,int cnt) {         if(cnt>n/2) return;         if(idx>=n) return;         if(cnt==n/2) {             int sum = 0;             int sum2 = 0;             for(int i=0;i<n;i++) {                 if(visited[i]) {                     for(int j=0;j<n;j++) {                         if(visited[j]) sum+=arr[i][j];                     }                 }else {                     for(int j=0;j<n;j++) {                         if(!visited[j]) sum2+=arr[i][j];                     }                 }             }             result = Math.min(result,Math.abs(sum-sum2));             return;         }         // 해당 식재료 고르기         visited[idx] = true;         solve(idx+1,cnt+1);         visited[idx] = false;         // 해당 식재료 안고르기         solve(idx+1,cnt);             } } Colored by Color Scripter

cs