[SWEA 4012] 요리사(C++)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH

SW Expert Academy

 

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <cstdio>
using namespace std;

int N;
int map[16][16];
bool chk[16];
int ans;


void Solve(int index, int cnt) {
	if (cnt == N / 2) {
		//계산
		vector<int> vectorA, vectorB;
		int A = 0, B = 0;
		for (int i = 0; i < N; i++) {
			if (chk[i] == 1) vectorA.push_back(i);
			else if(chk[i] == 0) vectorB.push_back(i);
		}
		
		for (int i = 0; i < vectorA.size() - 1; i++) {
			for (int j = i + 1; j < vectorA.size(); j++) {
				A += map[vectorA[i]][vectorA[j]] + map[vectorA[j]][vectorA[i]];
				B += map[vectorB[i]][vectorB[j]] + map[vectorB[j]][vectorB[i]];
			}
		}
		if (ans > abs(A - B))ans = abs(A - B);
		
		return;
	}
	for (int i = index; i < N; i++) {
		if (chk[i] == 0) {
			chk[i] = 1;
			Solve(i, cnt+1);
			chk[i] = 0;
		}
	}

}
int main() {
	//freopen("input.txt", "r", stdin);
	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		memset(chk, 0, sizeof(chk));
		ans = 987654321;
		cin >> N;
		//cout << N;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> map[i][j];
			}
		}
		
		Solve(1, 0);

		cout << "#" << tc << " " << ans << '\n';
	}

	return 0;
}