[BOJ 14889] 스타트와 링크

 N(짝수인 정수)가 주어졌을때 2팀으로 나누어 팀간의 능력치를 최소화하는 문제이다.

문제 풀이 : 팀을 나눌 수 있는 모든 경우를 다 본다음 능력치 차이의 최솟값을 출력했다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int N;
int ans;
void solve(vector <vector <int> > &map, vector<int> v) {
    int arr[2] = {0,0};
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j) continue;
 
            if (v[i] == v[j]) {
                arr[v[i]] += map[i + 1][j + 1];
            }
        }
    }
 
    if (ans > abs(arr[0] - arr[1])) { ans = abs(arr[0] - arr[1]); }
}
int main() {
    cin >> N;
 
    vector <vector <int> > map(N+1, vector<int>(N+1));
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
        }
    }
 
    vector <int> v;
    for (int i = 1; i <= N / 2; i++) {
        v.push_back(0);
        v.push_back(1);
    }
    
    sort(v.begin(), v.end());
    ans = 987654321;
    do {
        solve(map, v);
    }while(next_permutation(v.begin(), v.end()));
 
    cout << ans << '\n';
 
    return 0;
}