<Algorithm> 158. 요리사(SWExpert)

1. 요리사(SWExpert)

   사용 알고리즘 :  완전탐색

• 생각보다 오래걸렸던 문제..  조합 만드는 과정에서 로직이 살짝 햇갈렸다. 

문제에 대한 접근&생각

1. 모든 재료를 사용 -> 완전탐색!
2. 시간초과 -> 순열의 경우 중복되는 경우가 발생
3. 중복 경우 제거 -> 조합! 

내 코드 

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 56 57 58 59 60 61 62 63

import java.util.Scanner;   public class Solution {     static int n;     static int[][] map;     public static void main(String[] args) {         /******************************          * 음식 재료를 선택하는 경우의 수를           * 조합 형태로 구하여 각 요리에 해당하는          * 수치를 구한다.          *******************************/         Scanner sc = new Scanner(System.in);         int T = sc.nextInt();         for(int t = 1; t <= T; t++) {             n = sc.nextInt();             map = new int[n][n];             for(int i = 0; i < n; i++) {                 for(int j = 0; j < n; j++) {                     map[i][j] = sc.nextInt();                 }             }             min = Integer.MAX_VALUE;             visited = new boolean[n];             solve(0,0);                          System.out.println("#"+t+" "+min);         }     }     static boolean[] visited;     public static void solve(int deep,int idx) {         if(deep == n/2) {             check();             return;         }              for(int i = idx; i < n; i++) {             if(!visited[i]) {                 visited[i] = true;                 solve(deep+1,i+1);                 visited[i] = false;             }         }     }     static int min;     public static void check() {         //System.out.println(m);         //System.out.println(Arrays.toString(visited));         int totalA = 0;         int totalB = 0;         for(int i = 0; i < n-1; i++) {             for(int j = i+1; j < n; j++) {                     if(visited[i]&&visited[j]) {                     totalA += map[i][j]+map[j][i];                 }else if(!visited[i]&&!visited[j]){                     totalB += map[i][j]+map[j][i];                 }             }         }         min = Math.min(min, Math.abs(totalA-totalB));     }      }   Colored by Color Scripter

cs

 

참고 & 출처