[백준/14889] 스타트와 링크

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int map[20][20];
bool check[20];

int minv = 101;

void making_team(int index, int start, int n) {
	if (index == n / 2) {

		vector<int> team_a;
		vector<int> team_b;
		for (int i = 0; i < n; i++) {
			if (check[i]) {
				team_a.push_back(i);
			}
			else if (!check[i]) {
				team_b.push_back(i);
			}
		}

		int a_sum = 0;
		int b_sum = 0;

		for (int i = 0; i < team_a.size(); i++) {
			for (int j = 0; j < team_a.size(); j++) {
				if (i == j) continue;
				a_sum += map[team_a[i]][team_a[j]];
			}
		}

		for (int i = 0; i < team_b.size(); i++) {
			for (int j = 0; j < team_b.size(); j++) {
				if (i == j) continue;
				b_sum += map[team_b[i]][team_b[j]];
			}
		}

		if (abs(a_sum - b_sum) < minv) {
			minv = abs(a_sum - b_sum);
		}

		return;
	}
	for (int i = start; i < n; i++) {
		if (check[i]) continue;
		check[i] = true;
		making_team(index + 1, i, n);
		check[i] = false;
	}
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}

	making_team(0, 0, n);

	cout << minv << '\n';

	return 0;
}