[C++] 백준 15661번: 링크와 스타트

문제 링크

15661번: 링크와 스타트

문제 요약

두 선수가 같은 팀에 속했을 때, 그 팀이 얻게되는 능력치가 주어진다. 이때, 팀을 편성해서 두 팀의 능력치 차이의 최솟값을 찾아야 한다. 두 팀의 팀원 수는 달라도 되지만, 1명 이상의 팀원은 있어야 한다.

접근 방법

팀원 수가 달라도 되기 때문에 선수가 스타트에 속하는 경우, 링크에 속하는 경우를 모두 탐색해 주어야 합니다. 이 문제에서 N은 20 정도이고, $2^{20}$은 1048576입니다. 제한시간은 2초이기 때문에 완전탐색으로도 충분히 풀 수 있습니다.

코드

#include <bits/stdc++.h>
#define VPRT(x, type) copy(x.begin(), x.end(), ostream_iterator<type>(cout, " "))
#define ALL(x) x.begin(), x.end()
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define MAX 21

using namespace std;

int n, score[MAX][MAX], res = INT_MAX;
bool visited[MAX];

void update(void)
{
	vector<int> start, link;
	for (int i = 1; i <= n; i++)
	{
		if (visited[i])
			start.push_back(i);
		else
			link.push_back(i);
	}

	if (!start.size() || !link.size())
		return;

	int score1 = 0, score2 = 0;
	for (auto& i : start)
		for (auto& j : start)
			score1 += score[i][j];

	for (auto& i : link)
		for (auto& j : link)
			score2 += score[i][j];

	res = min(res, abs(score1 - score2));
}

void func(int idx)
{
	if (idx == n + 1)
	{
		update();
		return;
	}

	visited[idx] = true;
	func(idx + 1);
	visited[idx] = false;
	func(idx + 1);
}

int main(void)
{
	FASTIO;
	cin >> n;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> score[i][j];

	func(1);
	cout << res << endl;
	return 0;
}