문제 링크
https://www.acmicpc.net/problem/14889
14889번: 스타트와 링크
예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.
www.acmicpc.net
이전에 풀었던 스타트와 링크 문제를 순열을 이용해 다시 풀어봤다.
각 팀별로 수가 정해져있기 때문에 순열을 활용해 풀 수 있다. 참고로 링크와 스타트 문제 같은 경우에는 팀원의 수가 정확하게 정해져있지 않으므로 순열을 통한 풀이가 불가능하다.
전체 인원을 절반으로 나누어 앞의 절반은 0으로 뒤의 절반은 1로 마킹한 후 순열을 이용해 다음 순열을 넣어가며
전체를 탐색하도록 코드를 짰다.
매 정답이 구해질 때마다 기존의 값이랑 비교해서 더 값이 작다면 그 값이 정답으로 들어가도록 풀었다.
해결 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int solve(vector<vector<int> > &a, vector <int> &b){
vector <int> zero,one;
for(int i=0;i<n;++i){
if(b[i])
one.push_back(i);
else
zero.push_back(i);
}
int z=0; int o=0;
for(int i=0;i<n/2;++i){
for(int j=0;j<n/2;++j){
if(i==j)
continue;
z+=a[zero[i]][zero[j]];
o+=a[one[i]][one[j]];
}
}
int diff=abs(z-o);
return diff;
}
int main () {
ios_base::sync_with_stdio(0); cin.tie(NULL);
//input 받기
cin>>n;
vector<vector<int> > arr(n,vector<int>(n));
for(int i=0;i<n;++i){
for(int j=0; j<n; ++j){
cin>>arr[i][j];
}
}
//로직
vector <int> b(n);
for(int i=0;i<n/2;++i){
b[i]=1;
}
sort(b.begin(),b.end());
int ans=999999999;
do{
int diff=solve(arr,b);
if(ans>diff) ans=diff;
}while(next_permutation(b.begin(),b.end()));
//output
cout<<ans<<'\n';
return 0;
}