백준 14889 - 스타트와 링크

문제링크

• 백준 14889

문제설명

• 축구를 하기 위해 총 N 명의 사람이 모인다. (N은 항상 짝수)
• 팀을 스타트 팀과 링크 팀으로 나눈다.
• 사람에게 1번부터 N번까지 번호를 배정하고 능력치를 조사했다. S[i][j] 는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치를 의미한다. S[i][j] 와 S[j][i] 는 다를 수 있다.
• 팀의 능력치는 팀에 속한 모든 쌍의 능력치 S[i][j] 의 합이다.
• 두 팀의 능력치가 최소가 되는 경우를 구하라

문제접근

• 재귀호출을 통해 두 팀으로 나뉘면 각 팀의 능력치를 계산하고 차이를 반환한다.
• 두 팀으로 나누는 모든 경우의 수를 찾아 능력치 차이의 최솟값을 찾는다.

구현

#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>
#include <climits>

#define MAX_N 21
#define START 0
#define LINK 1
using namespace std;

int N;
int table[MAX_N][MAX_N];
int teamStatus[MAX_N];

int getAbility(vector<int> team)
{
	int ret = 0;
	for (int i = 0; i < team.size() - 1; i++) {
		for (int j = i + 1; j < team.size(); j++) {
			ret += (table[team[i]][team[j]] + table[team[j]][team[i]]);
		}
	}
	return ret;
}

int getDiff()
{
	vector<int> teamStart, teamLink;
	for (int i = 1; i <= N; i++) {
		if (teamStatus[i] == START) teamStart.push_back(i);
		else if (teamStatus[i] == LINK) teamLink.push_back(i);
	}
	return abs(getAbility(teamStart) - getAbility(teamLink));
}

int splitTeam(int v, int cnt)
{
	if (cnt == N / 2) {
		return getDiff();
	}

	int ret = INT_MAX;
	for (int i = v; i <= N; i++) {
		if (teamStatus[i] == LINK) continue;
		teamStatus[i] = LINK;
		ret = min(ret, splitTeam(i, cnt + 1));
		teamStatus[i] = START;
	}
	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> N;

	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			cin >> table[r][c];
		}
	}
	memset(teamStatus, 0, sizeof(teamStatus));
	cout << splitTeam(1, 0) << endl;
}