백준 14889 스타트와 링크

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

14889번: 스타트와 링크

 

- 난이도가 어렵진 않았지만, 디테일에 신경써야 하는 문제였다.

 

- 역시나 브루트포스 백트래킹 문제이다. 1번부터 최대 20번 선수까지 주어질 때, 각 선수가 A팀에 선택이 되던지, B팀에 선택이 되던지 두 가지의 경우의 수이고, 재귀의 깊이는 20을 넘지 못한다.(한 팀에 과반수의 인원이 들어가는 경우 바로 종결되기 때문.) 따라서, 2^20 이하의 연산량이 되므로 재귀적으로 구현이 가능하다.

 

- 각 팀의 구성원은 vector<int>로 관리하고, start팀에 선수를 넣고 DFS, 호출 종료 후 다시 POP 후 link팀에 선수를 넣고 DFS, 다시 POP하였다.

 

- 모든 팀원이 골고루 start와 link팀에 들어간 경우, 이중 for문을 통해 모든 경우의 수에 대해 능력치들을 더하고 두 팀의 능력치 합을 빼어 answer를 최소값으로 최신화하였다.

 

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

using namespace std;
int n;
int ability[21][21];
int answer = 2100000000;

void DFS(int cnt, vector<int>& start, vector<int>& link) {
	// 팀원이 균일하게 2등분되지 않으므로 종결
	if (start.size() > n / 2 || link.size() > n / 2) return;
	if (cnt > n) {
		int start_sum = 0;
		int link_sum = 0;
		for (int i = 0; i < n / 2; i++) {
			for (int j = i; j < n / 2; j++) {
				start_sum +=( ability[start[i]][start[j]] + ability[start[j]][start[i]]);
			}
		}
		for (int i = 0; i < n / 2; i++) {
			for (int j = i; j < n / 2; j++) {
				link_sum += (ability[link[i]][link[j]] + ability[link[j]][link[i]]);
			}
		}

		answer = min(answer, abs(start_sum - link_sum));
		return;
	}
	start.push_back(cnt);
	DFS(cnt + 1, start, link);
	start.pop_back();
	link.push_back(cnt);
	DFS(cnt + 1, start, link);
	link.pop_back();
}

int main() {
	vector<int> start, link;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> ability[i][j];
		}
	}
	DFS(1, start, link);
	cout << answer;
	return 0;
}