스타트와 링크

이것도 마찬가지로 순열을 이용했다.

일단 입력을 받은 후 0인 팀과 1인 팀으로 절반씩 나눠서 벡터에 push해주었다. 그리고 정렬을 한 뒤, next_permutation으로 모든 경우를 찾으면서 start 팀과 link 팀의 점수를 구해주었다. 그리고 차잇값이 가장 적은 값으로 갱신해주었다. 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <cmath>
using namespace std;
int s[25][25];

int main(){
	int n;
	cin>>n;
	
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cin>>s[i][j];
		}
	}
	
	vector <int> d;
	for(int i=0; i<n; i++){
		if(i<n/2) d.push_back(0);
		else d.push_back(1);
	}
	sort(d.begin(), d.end());
	int ans=2147000000;
	
	do{
		int a1=0;
		int a2=0;
		
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(d[i]==d[j]&&d[i]==0) a1+=s[i][j];
				else if(d[i]==d[j]&&d[i]==1) a2+=s[i][j];
			}
		}
		
		int val=abs(a1-a2);
		if(val<ans) ans=val;
	}while(next_permutation(d.begin(), d.end()));
	
	cout<<ans;
	return 0;
}