[15661] 링크와 스타트

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

15661번: 링크와 스타트

<문제>

가능한 모든 조합을 만들어주고, 이에대해 score를 계산해주어야 한다.

score의 계산이 매우 간단하지는 않지만,

i<j를 만족하는 모든 (i, j)를 찾을 수 있도록 2중 for를 돌린다고 생각하면 편하다. 

모든 (i, j)에 대해서, i와 j가 같은팀일때 input[i][j]와 input[j][i]를 해당 팀에 누적합하면 된다.

 

같은팀에 대한 판별은, next_permutation으로 0과 1로 이루어진 순열을 뽑아내주었고,

각 팀의 최소인원이 1명이상이여야 한다는 조건외에 추가적인 인원에대한 조건이 없으므로

한 팀에 몰릴 수 있는 인원이 [1, n-1]까지, for를 한번 돌려주고 그 안에 해당 개수(nCr)만큼 탐색한다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int ans = 54321, n, a[21][21], check[21], sum[2];
int main(void) {
    int i, j, k;
    cin >> n;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++) cin >> a[i][j];
    for (i = 1; i <= n - 1; i++) {
        for (j = 1; j <= i; j++) check[j] = 0;
        for (j = i + 1; j <= n; j++) check[j] = 1;
        do {
            memset(sum, 0, sizeof(sum));
            for (j = 1; j <= n; j++)
                for (k = 1; k <= n; k++)
                    if (j != k && check[j] == check[k])
                        sum[check[j]] += a[j][k];
            ans = min(abs(sum[0] - sum[1]), ans);
        } while (next_permutation(check + 1, check + n + 1));
    }
    cout << ans;
    return 0;
}