자이의 프로그래밍
스타트와 링크 본문
이것도 마찬가지로 순열을 이용했다.
일단 입력을 받은 후 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;
}