[BOJ/C++] 14889(스타트와 링크)

1. Link

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

2. 풀이 과정

1. 2팀으로 나누되, 같은 팀의 인원은 서로의 능력치 값을 더해야 함 -> 백트래킹

• 단순 nC2 형태의 문제라 생각했지만 S[i][j]및 S[j][i] 등 가중치가 다르기 때문에 nC2라는 경우의 수를 가지는 백트래킹으로 풀기로 했습니다.

• 예제를 기반으로 풀이를 설명해보겠습니다.
  

팀 순서는
1. (1,2), (3,4)
2. (1,3), (2,4)
3. (1,4), (2,3)
순으로 살펴보겠습니다.(가능한 모든 경우의 수는 3C2 = 3이겠네요)

1. 먼저 1번 상황을 살펴보면 다음과 같습니다.
   
   S[1][2] + S[2][1] = 1 + 4 = 5
   S[3][4] + S[4][3] = 2 + 5 = 7
   따라서 두 팀간의 능력치 차이는 7 - 5 = 2가 됩니다.

2. 2번도 비슷하게 이어집니다.
   
   S[1][3] + S[3][1] = 2 + 7 = 9
   S[2][4] + S[4][2] = 6 + 4 = 10
   따라서 두 팀간의 능력치 차이는 10 - 9 = 1이 됩니다.

3. 마지막으로 3번 케이스입니다.
   
   S[1][4] + S[4][1] = 3 + 3 = 6
   S[2][3] + S[3][2] = 1 + 5 = 6
   따라서 두 팀간의 능력치 차이는 6 - 6 = 0이 됩니다.

각 케이스에서 능력치 차이는 2, 1, 0이 나왔고, 따라서 그 중에서 가장 최소값인 0이 정답이 되겠습니다.

3. 정답 코드

#include <iostream>
using namespace std;

int n, answer = 987654321;
int s[21][21];
bool vis[21]{0};

int abs(int a, int b) {
	if (a >= b) return a - b;
	return b - a;
}

void input() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			cin >> s[i][j];
		}
	}
}

void rec(int st, int cnt) {
	if (cnt == (n >> 1)) {
		int team1 = 0, team2 = 0;
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				if (i == j) continue;
				if (vis[i] && vis[j]) {
					team1 += s[i][j] + s[j][i];
				}
				else if (!vis[i] && !vis[j]) {
					team2 += s[i][j] + s[j][i];
				}
			}
		}
		int dif = abs(team1 - team2);
		if (answer > dif) answer = dif;
		return;
	}
	for (int i = st; i <= n; ++i) {
		if (vis[i]) continue;
		vis[i] = 1;
		rec(i + 1, cnt + 1);
		vis[i] = 0;
	}
}

void solution() {
	input();
	rec(1, 0);
	cout << (answer >> 1);
}

int main() {
	cin.tie(0), cout.tie(0);
	ios_base::sync_with_stdio(0);
	solution();
	return 0;
}