SWEA 4012シェフ



すべての可能な状況を組み合わせて計算し、条件に合えば更新すればよい.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Solution {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static int[][] food;
	static int[] numbers;
	static boolean[] isSelected;
	static int N, R, min = Integer.MAX_VALUE, count_combi = 0, count_combi_max;

	public static void combination(int cnt, int start) { // 현재 자리에 수 뽑기.
		if (cnt == N / 2) {
			//System.out.println(Arrays.toString(numbers));
			//System.out.println(Arrays.toString(isSelected));
			if(count_combi == count_combi_max / 2)return;
			count_combi++;
			calc();

			return;
		}

		// 입력받은 모든 수를 현재 자리에 넣어보기(유도파트)
		for (int i = start; i < N; i++) {
			isSelected[i] = true;
			numbers[cnt] = i;
			combination(cnt + 1, i + 1);
			isSelected[i] = false;
		}

	}

	public static int calc() {
		int[] com = new int[N / 2];
		int[] com_remain = new int[N / 2];
		int c = 0, sumofC = 0;
		int c_remain = 0, sumofC_remain = 0;
		for (int i = 0; i < N; i++) {
			if (isSelected[i])
				com[c++] = i;
			else
				com_remain[c_remain++] = i;
		}
		for (int i = 0; i < N / 2 - 1; i++) {
			for (int j = i + 1; j < N / 2; j++) {
				sumofC += food[com[i]][com[j]] + food[com[j]][com[i]];
				sumofC_remain += food[com_remain[i]][com_remain[j]] + food[com_remain[j]][com_remain[i]];
			}
		}
		//System.out.println(sumofC + " " + sumofC_remain);
		if (Math.abs(sumofC_remain - sumofC) < min) {
			min = Math.abs(sumofC_remain - sumofC);
		}

		return 0;
	}

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			R = N / 2;
			food = new int[N][N];
			isSelected = new boolean[N];
			numbers = new int[N / 2];

			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < N; j++) {
					food[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			count_combi = 0;
			count_combi_max = 1;
			for(int i = N; i > N / 2; i-- ) {
				count_combi_max *= i;
			}
			min = Integer.MAX_VALUE;
			combination(0, 0);

			System.out.println("#" + tc + " " + min);
		}
	}
}