문제 분석

• 식성이 비슷한 2명의 손님
• 식재료 N / 2 → 2개의 요리 (A, B)
• 맛의 차이가 최소가 되도록 재료를 배분
• 식재료 i & j의 시너지 Sij가 주어짐
  (1 ≤ i ≤ N, 1 ≤ j ≤ N, i ≠ j)
• A음식과 B음식을 만들 때,
  
  두 음식 간의 맛의 차이가 최소가 되는 경우를 찾고 그 최솟값을 정답으로 출력
  

입출력

 T
 N: even num  (4 ≤ N ≤ 16)
 N개의 줄에는 N * N개의 시너지 Sij값
 
10
4
0 5 3 8
4 0 4 1
2 5 0 3
7 2 3 0

문제 풀이 방법

1. A 요리에 사용할 수 있는 재료의 조합 찾기
2. B 요리에 사용할 수 있는 재료의 조합 찾기

• A요리에서 사용하고 남은 재료들의 조합

3. 음식의 맛

• 같은 식재료는 같이 사용하지 않음
• 문제조건: (1 ≤ i ≤ N, 1 ≤ j ≤ N, i ≠ j)
  시너지 테이블에도 없음
• 각 조합에서 i=j 경우를 제외한 순열을 만들어 더하기

4. 최적의 조합 찾기

• Min (|A음식의 맛 - B음식의 맛|s)

코드 작성

public class Solution {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=T; t++) {
			
			// [input]
			int N = Integer.parseInt(br.readLine());
			int[][] sTable = new int[N+1][N+1];
			
			for(int r=1; r<=N; r++) {
				String[] temp = br.readLine().split(" "); 
				for(int c=1; c<=N; c++) {
					sTable[r][c] = Integer.parseInt(temp[c-1]);
				}
			}
			
			// [logic]
			List<List<Integer>> IngredientsForA = choosenIngredientsForA(N);
			List<List<Integer>> IngredientsForB = choosenIngredientsForB(N, IngredientsForA);
			
			List<Integer> tastesOfFoodA = tastesOfFood(sTable,IngredientsForA);
			List<Integer> tastesOfFoodB = tastesOfFood(sTable,IngredientsForB);
			
			int min = findBestCombi(tastesOfFoodA, tastesOfFoodB);
				
			System.out.printf("#"+t+" "+min+"\n");
			}// for: t
			
			
	}// main
		

		
	// A 요리 사용할 수 있는 재료의 조합 : N개의 식재료 중 N/2개 선택
	public static List<List<Integer>> choosenIngredientsForA (int N) {
		List<List<Integer>> ij = new ArrayList<>();
		
		int r = N/2;
		
		dfs(N,r,1, new ArrayList<>(), ij);
		
		return ij;
	} 
	
	
	public static void dfs(int N, int r, int start, List<Integer> current, List<List<Integer>> ij) {
		// base-case
		if(current.size()==r) {
			// XX ij.add(current) XX
			ij.add(new ArrayList<>(current));
		}
		
		// recursion
		for(int i=start; i<=N; i++) {
			current.add(i);
			dfs(N,r,i+1, current,ij);
			current.remove(current.size()-1);
			
		}
	}
	
	// B요리에 사용할 수 있는 재료의 조합
	public static List<List<Integer>> choosenIngredientsForB (int N, List<List<Integer>> choosenIngredientsForA ){
		List<List<Integer>> choosenIngredientsForB = new ArrayList<>();
		
		for( List<Integer> ingredientsforA : choosenIngredientsForA) {
			List<Integer> ingredientsforB = new ArrayList();
			for(int i=1; i<=N; i++) {
				if(!ingredientsforA.contains(i)) {
					ingredientsforB.add(i);
				}
			}
			choosenIngredientsForB.add(ingredientsforB);
		}
		
		return choosenIngredientsForB;
	}
	
	
	// 음식의 맛
	// 같은 식재료는 같이 사용 x 
	// 문제 조건: (1 ≤ i ≤ N, 1 ≤ j ≤ N, i ≠ j)
	// 각 조합에서 (i=j)를 제외한 순열을 만들어 더하기
	public static List<Integer> tastesOfFood (int[][] sTable, List<List<Integer>> choosenIngredients) {
		
		List<Integer> result = new ArrayList<>();
		
		for(List<Integer> ingredients: choosenIngredients) {
			int sum = 0;
			int n = ingredients.size();
			
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
					// i,j 값이 아니라 그 번째의 값!
					int ith = ingredients.get(i);
					int jth = ingredients.get(j);
					if(ith != jth) {
						sum+= sTable[ith][jth];
					}
				}
			}
			result.add(sum);
		}
		
		return result;
	
	}
	
	public static int findBestCombi (List<Integer>tastesOfFoodA,List<Integer>tastesOfFoodB ) {
		int min = Integer.MAX_VALUE;
		for(int i=0; i<tastesOfFoodA.size();i++) {
			int abs = Math.abs(tastesOfFoodA.get(i)-tastesOfFoodB.get(i));
			if(abs < min) min = abs;
		}
		return min;
	}
	
	
}

시간복잡도 & 개선 방향

$O(N ^2⋅C(N,N/2))$

개선 포인트

• 현재 코드에서 요리 B에 사용할 재료 조합을 만들 때, choosenIngredientsForA 리스트를 반복하며 contains() 메서드를 사용
• ArrayList의 contains()는 $O(N)$의 시간 복잡도를 가지므로, 이 과정이 반복되면 성능이 저하됨
• 가장 큰 비효율성은 모든 재료 조합을 메모리에 저장한 뒤,
  다시 반복문을 돌며 맛을 계산하는 방식에 있음

백트래킹 활용 -> 계산 과정 최적화

• dfs 함수가 조합을 하나씩 만들어나가는 동시에 요리 A와 B의 맛 점수를 계산하고, 두 점수 차이의 최솟값을 갱신하도록 하는 방법
• 백트래킹 방식을 적용하면, 재료를 선택할 때 배열(boolean[] used)을 사용해 어떤 재료가 사용되었는지 표시하는 것이 훨씬 효율적임
  used 배열은 $O(1)$의 시간 복잡도로 재료의 사용 여부를 확인할 수 있어 contains()보다 훨씬 빠름

1) 메모리 효율성
List<List>를 사용해 모든 조합을 저장했던 기존 코드와 달리,
이 코드는 재료의 사용 여부를 나타내는 boolean 배열(visited) 하나만 사용

2) 시간 효율성
findMinDifference 재귀 함수가 N개의 재료 중 N/2개를 선택하는 모든 조합을 생성
각 조합이 완성될 때마다 (count == N / 2), calculateTasteDifference 메서드를 호출하여 맛 점수를 계산하고 최솟값을 갱신
이 방식은 중간에 불필요한 리스트 생성 및 탐색 과정을 모두 제거할 수 있음

public class Solution {
   static int N;
   static int[][] sTable;
   static boolean[] visited;
   static int minDifference;

   public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       int T = Integer.parseInt(br.readLine());

       for (int t = 1; t <= T; t++) {
           N = Integer.parseInt(br.readLine());
           sTable = new int[N + 1][N + 1];
           visited = new boolean[N + 1];
           minDifference = Integer.MAX_VALUE;

           for (int r = 1; r <= N; r++) {
               String[] temp = br.readLine().split(" ");
               for (int c = 1; c <= N; c++) {
                   sTable[r][c] = Integer.parseInt(temp[c - 1]);
               }
           }

           findMinDifference(1, 0);

           System.out.printf("#" + t + " " + minDifference + "\n");
       }
   }

   /**
    * N개의 재료 중 N/2개를 선택하는 모든 조합을 탐색
    * 요리 A와 B의 맛 점수 차이의 최솟값을 찾기
    *
    * @param start 현재 재료 선택을 시작할 인덱스
    * @param count 현재까지 선택한 재료의 수
    */
   public static void findMinDifference(int start, int count) {
       if (count == N / 2) {
           calculateTasteDifference();
           return;
       }

       for (int i = start; i <= N; i++) {
           visited[i] = true;
           findMinDifference(i + 1, count + 1);
           visited[i] = false;
       }
   }

   /**
    * 선택된 재료 (visited가 true)와 선택되지 않은 재료 (visited가 false)를
    * 각각 요리 A와 B로 나누어 맛 점수를 계산하고 차이의 최솟값을 갱신
    */
   public static void calculateTasteDifference() {
       int tasteA = 0;
       int tasteB = 0;

       for (int i = 1; i <= N; i++) {
           for (int j = 1; j <= N; j++) {
               // 요리 A의 맛 점수 계산
               if (visited[i] && visited[j]) {
                   tasteA += sTable[i][j];
               }
               // 요리 B의 맛 점수 계산
               else if (!visited[i] && !visited[j]) {
                   tasteB += sTable[i][j];
               }
           }
       }

       int diff = Math.abs(tasteA - tasteB);
       minDifference = Math.min(minDifference, diff);
   }

??? & !!!

1. 참조 자료형: 리스트 추가 방법

• ij.add(current)라고 하면 current 리스트의 참조(주소) 가 그대로 저장됨
• new ArrayList<>(current)를 사용해서 current의 복사본 넣기

2. 백트래킹 패턴

for(int i=start; i<=N; i++) {
	current.add(i);
	dfs(N, r, i+1, current, ij);
	current.remove(current.size()-1);
}                          

• 선택(do) → 탐색(dfs) → 원복(undo)
• 익히는 ing