[BOJ] 14889 - 스타트와 링크

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

---

[알고리즘풀이]

백트레킹 기법을 이용하여, ( N / 2 ) 명을 뽑는 모든 경우의 수에 대해 Team 능력치를 구하고, 차이를 계산한다.

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

using namespace std;

int m = 1000000000, n;
int map[20][20];

void bt(int, int, vector<int>);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];
	vector<int> v;
	for (int i = 0; i < n / 2; i++) {
		v.push_back(i);
		bt(1, i, v);
		v.pop_back();
	}
	cout << m;
}

void bt(int k, int l, vector<int> v) {
	if (k == n / 2) {
		int t1 = 0, t2 = 0;
		bool c[20] = {};
		for (int i = 0; i < v.size(); i++)
			c[v[i]] = true;
		vector<int> v2;
		for (int i = 0; i < n; i++)
			if (c[i] == false)
				v2.push_back(i);
		
		for (int i = 0; i < v.size(); i++)
			for (int j = 0; j < v.size(); j++)
					t1 += map[v[i]][v[j]];

		for (int i = 0; i < v2.size(); i++)
			for (int j = 0; j < v2.size(); j++)
					t2 += map[v2[i]][v2[j]];
		if (abs(t1 - t2) < m)
			m = abs(t1 - t2);
		return;
	}

	for (int i = l + 1; i < n; i++) {
		v.push_back(i);
		bt(k + 1, i, v);
		v.pop_back();
	}
	return;
}

---