백준 14889 C++

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

이 문제에서 고민한 점은 어떻게 2개의 팀으로 나눌것인가만 해결하면 된다고 생각했다.

처음에 팀 조합을 만들어야하니 Bit masking도 생각을 했었다가 재귀로 더 쉽게 할 수 있을거 같아서 폐기했다.

물론 비트마스킹으로도 비트가 켜져있는게 몇개인지로 변경한다면 충분히 해결할 수 있을 것으로 생각되긴한다.

N <= 20 밖에 되지 않아서 2^20도 무난히 가능할 것이라 판단해서 재귀로 모든 경우에 대해서 돌렸다.

 

#include <bits/stdc++.h>

using namespace std;

int n;		//n < 20 짝수
int result = 987654321;
vector<vector<int>> v(21);

int diff(string a, string b)
{
	int asum = 0, bsum = 0;

	//aTeam
	for (int i = 0; i < a.size(); i++) {
		for (int j = i + 1; j < a.size(); j++) {
			asum = asum + v[a[i] - '0'][a[j] - '0'] + v[a[j] - '0'][a[i] - '0'];
		}
	}

	for (int i = 0; i < b.size(); i++) {
		for (int j = i + 1; j < b.size(); j++) {
			bsum = bsum + v[b[i] - '0'][b[j] - '0'] + v[b[j] - '0'][b[i] - '0'];
		}
	}

	return abs(asum - bsum);
}

void makeTeam(int index, string a, string b)
{
	if (index > n) return;
	if (a.size() > n / 2 || b.size() > n / 2) return;		//절반으로 이제 안나눠진다.

	if (a.size() == n / 2 && b.size() == n/2) {		//팀이 모두 짜여졌다.
		int comp = diff(a, b);
		result = min(comp, result);

		//cout << "A Team : " << a << "  B Team" << b << "    result :" << result << "\n";

		return;
	}

	char c = index + '0';
	makeTeam(index + 1, a+c, b);			//a팀에 현재 index가 들어간다
	makeTeam(index + 1, a, b + c);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;

	int temp;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> temp;
			v[i].push_back(temp);
		}
	}

	string a = "", b="";
	makeTeam(0, a, b);

	cout << result;
}