스타트와 링크

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

14889번: 스타트와 링크

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int n;
int g[21][21];
int result=2147000000;
int pick[21];
int team1[10];
int team2[10];


void update() {
	int t1_size = 0, t2_size = 0;
	for (int i = 1; i <= n; i++) {
		if (pick[i] == 1) {
			team1[++t1_size] = i;
		}
		else team2[++t2_size] = i;
	}
	int s1=0, s2=0; //각 팀의 합
	for (int i = 1; i <= n / 2; i++) {
		for (int j = i + 1; j <= n / 2; j++) {
			s1 += g[team1[i]][team1[j]] + g[team1[j]][team1[i]];
			s2 += g[team2[i]][team2[j]] + g[team2[j]][team2[i]];
		}
	}
	result = min(result, abs(s1 - s2));
}

void DFS(int cur, int cnt) {
	if (cnt == n / 2) {
		update();
		return;
	}
	else {
		for (int i = cur; i <= n; i++) {
			pick[i] = 1;
			DFS(i + 1, cnt + 1);
			pick[i] = 0;
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> g[i][j];
		}
	}
	DFS(1, 0);
	cout << result << "\n";
	return 0;
}