백준 14889번 C++

#include<iostream>

#include<vector>

#include<algorithm>

using namespace std;

const int MAX = 21;

int n;

int arr[MAX][MAX];

int minsum = 987654321;

void dfs(string team, int start, int link) {

if (start < n/2)

dfs(team + "s", start + 1, link);

if (link < n/2)

dfs(team + "l", start, link + 1);

if (team.size() == n) {

vector<int> startteam, linkteam;

for (int i = 0; i < team.size(); i++) {

if (team[i] == 's')

startteam.push_back(i);

else

linkteam.push_back(i);

}

int startsum = 0;

int linksum = 0;

for (int i= 0; i < n/2-1; i++) {

for (int j = i + 1; j < n / 2; j++) {

startsum += arr[startteam[i]][startteam[j]] + arr[startteam[j]][startteam[i]];

linksum += arr[linkteam[i]][linkteam[j]] + arr[linkteam[j]][linkteam[i]];

}

}

minsum = min(minsum, abs(startsum - linksum));

return;

}

}

int main(void) {

cin >> n;

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

cin >> arr[i][j];

}

}

dfs("", 0, 0);

cout << minsum << endl;

return 0;

}