14889 스타트와 링크

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

팀을 절반씩 나누는 모든 경우를 만들어서 능력치의 차이를 계산해본다. 최대 20C10 = 184756 이므로 시간 내에 충분히 수행될 수 있음을 알 수 있다.

#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#define INF 987654321
using namespace std;
 
int n,a[20][20],v[20],ans=INF;
 
void solve()
{
    vector<int> start,link;
    for(int i=0;i<n;i++)
        v[i]?start.push_back(i):link.push_back(i);
    int s1=0,s2=0;
    for(int i=0;i<n/2-1;i++) for(int j=i+1;j<n/2;j++)
        s1+=a[start[i]][start[j]]+a[start[j]][start[i]];
    for(int i=0;i<n/2-1;i++) for(int j=i+1;j<n/2;j++)
        s2+=a[link[i]][link[j]]+a[link[j]][link[i]];
    ans=min(ans,abs(s1-s2));
}
 
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&a[i][j]);
    for(int i=0;i<n/2;i++) v[i]=-1;
    do solve(); while(next_permutation(v,v+n));
    printf("%d\n",ans);
    return 0;
}