[Java] swea 4012 요리사

[Java] swea 4012 요리사

 

조합문제!

N개의 식재료 중에 N/2개를 뽑으면, 

1, 2, 3, ... , N/2 번의 시너지를 모두 더한다.

S12 + S13 + S14 +... + S23 + ... 

 

이런 걸 안 뽑힌 애들도 더해서 차이를 구해주고

제일 작은 차이를 return 하면 된다.

 

package 삼성합격;

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

public class 모의SW_4012_요리사 {
	static int N, MIN;
	static int[][] grid;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int testcase = 1; testcase <= T; testcase++) {
			MIN = Integer.MAX_VALUE;
			N = Integer.parseInt(br.readLine());
			grid = new int[N][N];
			numbers = new int[N/2];
			selected = new boolean[N];
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine()); 
				for (int j = 0; j < N; j++) {
					grid[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			solve(0, 0);
			
			System.out.println("#" + testcase + " " + MIN);
			
		} // tc
		
	} // main

	
	static int[] numbers;
	static boolean[] selected;
	private static void solve(int start, int cnt) {
		if(cnt == N/2) {
			int[] num2 = new int[N/2];
			int idx = 0;
			for (int i = 0; i < N; i++) {
				if(!selected[i]) num2[idx++] = i;
			}
			int sum1 = 0, sum2 = 0;
			for (int i = 0; i < N/2-1; i++) {
				for (int j = i+1; j < N/2; j++) {
					sum1 += grid[numbers[i]][numbers[j]];
					sum1 += grid[numbers[j]][numbers[i]];
				}
			}
			for (int i = 0; i < N/2-1; i++) {
				for (int j = i+1; j < N/2; j++) {
					sum2 += grid[num2[i]][num2[j]];
					sum2 += grid[num2[j]][num2[i]];
				}
			}
			
			int result = Math.abs(sum1-sum2);
			if(MIN > result) MIN = result;
			
			return;
		}
		
		for (int i = start; i < N; i++) {
			numbers[cnt] = i;
			selected[i] = true;
			solve(i+1, cnt+1);
			selected[i] = false;
		}
	}
	
}