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

출처 : https://www.acmicpc.net/problem/15661

 

백트래킹으로 문제를 해결하였다.

가능한 링크 팀의 경우의 수를 모두 구하고, 링크 팀의 팀원이 아니라면 스타트 팀에 넣고, 각각의 경우마다 두 팀의 점수의 차의 절댓값 중 가장 작은값을 찾았다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int n;
vector<vector<int>> v(21, vector<int>(21, 0));
vector<int> link;
int ans = 987654321;

int gap() {
	int score_link = 0;
	int score_start = 0;
	vector<int> start;
	for (int i = 1; i <= n; i++) {
		if (find(link.begin(), link.end(), i) == link.end()) {
			start.push_back(i);
		}
	}
	for (int i = 0; i < link.size(); i++) {
		for (int j = 0; j < link.size(); j++) {
			if (i == j) continue;
			score_link += v[link[i]][link[j]];
		}
	}
	for (int i = 0; i < start.size(); i++) {
		for (int j = 0; j < start.size(); j++) {
			if (i == j) continue;
			score_start += v[start[i]][start[j]];
		}
	}
	return abs(score_link - score_start);
}

void BT(int index) {
	if (index > n) return;
	for (int i = index; i <= n; i++) {
		link.push_back(i);
		ans = min(ans, gap());
		BT(i + 1);
		link.pop_back();
	}
}

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

	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> v[i][j];
		}
	}
	BT(1);
	cout << ans;
};