백준 14889번 : 스타트와 링크

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
#include <algorithm>
using namespace std;

void divideTeams(const vector<vector<int>>& S, int N, vector<int>& team, int idx, int count, int& result) {
    if (count == N / 2) {
        vector<int> linkTeam;
        for (int i = 1; i <= N; i++) {
            if (find(team.begin(), team.end(), i) == team.end()) {
                linkTeam.push_back(i);
            }
        }

        int startAbility = 0, linkAbility = 0;
        for (int i = 0; i < N / 2; i++) {
            for (int j = i + 1; j < N / 2; j++) {
                startAbility += S[team[i] - 1][team[j] - 1] + S[team[j] - 1][team[i] - 1];
            }
        }

        for (int i = 0; i < N / 2; i++) {
            for (int j = i + 1; j < N / 2; j++) {
                linkAbility += S[linkTeam[i] - 1][linkTeam[j] - 1] + S[linkTeam[j] - 1][linkTeam[i] - 1];
            }
        }

        result = min(result, abs(startAbility - linkAbility));
        return;
    }

    for (int i = idx; i <= N; i++) {
        team.push_back(i);
        divideTeams(S, N, team, i + 1, count + 1, result);
        team.pop_back();
    }
}

int main() {
    int N;
    cin >> N;
    vector<vector<int>> S(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> S[i][j];
        }
    }

    int result = INT_MAX;
    vector<int> team;
    divideTeams(S, N, team, 1, 0, result);
    cout << result << endl;

    return 0;
}