4012. [모의 SW 역량테스트] 요리사 ----- 권장하지 않는 매우 더러운 풀이

Solution.java

import java.util.*;
import java.io.*;

public class Solution {
	
	public static void swap(int[] arr, final int i1, final int i2) {
		int tmp = arr[i1];
		arr[i1] = arr[i2];
		arr[i2] = tmp;
	}
	
	public static boolean nextPermutation(int[] arr) {
		final int indexEnd = arr.length - 1;
		
		// 1. 피벗 검색
		int indexPivot = -1;
		for (int i = indexEnd; i >= 1; --i) {
			if (arr[i-1] < arr[i]) {
				indexPivot = i - 1;
				break;
			}
		}
		if (indexPivot == -1) {
			return false;
		}
		
		// 2. 피벗과 바꿀 요소 찾고 교환
		int indexToSwap = -1;
		for (int i = indexEnd; i > indexPivot; --i) {
			if (arr[i] > arr[indexPivot]) {
				indexToSwap = i;
				break;
			}
		}
		swap(arr, indexPivot, indexToSwap);
		
		// 01 2 34567
		// 12 3 45678		
		// 3. 나머지 반전
		for (int i = 0; i < Math.floor((indexEnd - indexPivot) / 2); ++i) {
			swap(arr, indexPivot + 1 + i, indexEnd - i);
		}
		return true;
	}
	
	public static void printArr(int[] arr) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < arr.length; ++i) {
			sb.append(arr[i]);
			sb.append(' ');
		}
		System.out.println(sb);
	}
	
	public static int[] getSynergies(
			
			final int[][] s, 
			final int[] combinationOfIngredients, 
			int half) {
		
		final int[] ret = new int[2];
		
		//
		final int[] permBitmaskForSingleSynergyLeft = new int[half];
		final int[] permBitmaskForSingleSynergyRight = new int[half];
		for (int i = 0; i < 2; ++i) {
			permBitmaskForSingleSynergyLeft[i] = 0;
			permBitmaskForSingleSynergyRight[i] = 0;
		}
		for (int i = 2; i < half; ++i) {
			permBitmaskForSingleSynergyLeft[i] = 1;
			permBitmaskForSingleSynergyRight[i] = 1;
		}
		//

		// a (left)
		int sum = 0;
		do {
			final int[] combinationForSingleSynergy = new int[2];
			for (int i = 0, j = 0; i < half; ++i) {
				if (permBitmaskForSingleSynergyLeft[i] == 0) {
					combinationForSingleSynergy[j++] = combinationOfIngredients[i];
					//System.out.println(combinationOfIngredients[i]); // debug
				}
			}
			sum += s[combinationForSingleSynergy[0]][combinationForSingleSynergy[1]] + s[combinationForSingleSynergy[1]][combinationForSingleSynergy[0]];
		} while (nextPermutation(permBitmaskForSingleSynergyLeft));
		ret[0] = sum;
		
		// b (right)
		sum = 0;
		do {
			final int[] combinationForSingleSynergy = new int[2];
			for (int i = 0, j = 0; i < half; ++i) {
				if (permBitmaskForSingleSynergyRight[i] == 0) {
					combinationForSingleSynergy[j++] = combinationOfIngredients[i + half];
				}
			}
			sum += s[combinationForSingleSynergy[0]][combinationForSingleSynergy[1]] + s[combinationForSingleSynergy[1]][combinationForSingleSynergy[0]];
		} while (nextPermutation(permBitmaskForSingleSynergyRight));
		ret[1] = sum;
		
		return ret;
	}
	
	public static void main(String args[]) throws IOException {
		final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		final int nTestCases = Integer.parseInt(br.readLine());	
		final StringBuilder ret = new StringBuilder();
		
		for (int _i = 0; _i < nTestCases; ++_i ) { // for a test case
			
			final int n = Integer.parseInt(br.readLine());
			final int[][] s = new int[n][n];
			for (int i = 0; i < n; ++i) {
				final StringTokenizer st = new StringTokenizer(br.readLine());
				for (int j = 0; j < n; ++j) {
					s[i][j] = Integer.parseInt(st.nextToken());
				}
			} // for int[][] s
			final int[] permBitmaskForCombinationOfIngredients = new int[n];
			final int half = n / 2;
			for (int i = 0; i < half; ++i) {
				permBitmaskForCombinationOfIngredients[i] = 0;
			} // left
			for (int i = half; i < permBitmaskForCombinationOfIngredients.length; ++i) {
				permBitmaskForCombinationOfIngredients[i] = 1;
			} // right

			int min = Integer.MAX_VALUE;
			do {
				final int[] combinationOfIngredients = new int[n]; // 순서 무시 조합 // 앞 반은 a, 뒤 반은 b
				// 비트마스크에서 재료 조합 추출
				//printArr(permBitmaskForCombinationOfIngredients); // debug
				for (int i = 0, j = 0; i < permBitmaskForCombinationOfIngredients.length && j < n; ++i) { // i for index to read, j for index to write
					if (permBitmaskForCombinationOfIngredients[i] == 0) {
						combinationOfIngredients[j++] = i;
						//System.out.println(i); // debug
					}
				}
				//printArr(combinationOfIngredients); // debug
				for (int i = 0, j = half; i < permBitmaskForCombinationOfIngredients.length && j < n; ++i) {
					if (permBitmaskForCombinationOfIngredients[i] == 1) {
						combinationOfIngredients[j++] = i;
						//System.out.println(i); // debug
					}
				}
				//printArr(ingredientsPermExtractedUsingBitmask); // debug
				
				//System.out.println("getSynergies in"); // debug
				int[] ab = getSynergies(s, combinationOfIngredients, half);
				//System.out.println("getSynergies out"); // debug
				int a = ab[0];
				int b = ab[1];
				//if (min > Math.abs(a - b)) { // debug
					//printArr(ingredientsPermExtractedUsingBitmask); // debug
					min = Math.min(min, Math.abs(a - b));
					//System.out.println(min); // debug
				//} // debug
				
			} while (nextPermutation(permBitmaskForCombinationOfIngredients));
			
			ret.append('#');
			ret.append(_i + 1);
			ret.append(' ');
			ret.append(min);
			ret.append('\n');
			//System.out.println(ret); // debug
		} // test case
		
		System.out.println(ret);
		
	} // main()
} // public class