[14889] 스타트와 링크

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

14889번: 스타트와 링크

<문제>

n이 짝수이고, 각팀당 인원수를 n/2로 만들어야 한다. 20C10개의 경우의 수를 완전탐색.

하나의 경우에 수에서의 score는 2중for로 간단하게 계산할 수 있다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, ans = 1e9, a[21][21];
int main(void) {
    cin >> n;
    int i, j;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) cin >> a[i][j];
    vector<int> base(n, 1);
    int mid = n / 2;
    for (i = 0; i < mid; i++) base[i] = 0;
    do {
        vector<int> sum(2);
        for (i = 0; i < n - 1; i++)
            for (j = i + 1; j < n; j++)
                if (base[i] == base[j]) sum[base[i]] += (a[i][j] + a[j][i]);
        ans = min(abs(sum[1] - sum[0]), ans);
    } while (next_permutation(base.begin(), base.end()) == true);
    cout << ans;
    return 0;
}