[백준/BOJ] 14889 스타트와 링크

문제 : 14889 스타트와 링크

14889번: 스타트와 링크

짝수인 수의 사람이 주어졌을 때, 절반으로 나눠 각 팀 능력치

합의 차이가 최소일 때 그 값을 출력하는 문제이다.

next_permutation을 사용해 모든 경우의 수를 구하고 

각 경우의 능력치 차이를 구해 최솟값을 갱신한 후 출력하면 된다.

---

Code

#include <bits/stdc++.h>
#define ll long long
#define INF 987654321
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll N, arr[25][25], ans=INF;
    vector<ll> chk;
    cin >> N;
    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            cin >> arr[i][j];
        }
    }
    for (int i=0;i<N/2;i++){
        chk.push_back(0);
    }
    for (int i=0;i<N/2;i++){
        chk.push_back(1);
    }
    do{
        ll cnt[2]={0,};
        for (int i=0;i<N;i++){
            for (int j=i+1;j<N;j++){
                if (chk[i]==chk[j]){
                    cnt[chk[i]]+=arr[i][j]+arr[j][i];
                }
            }
        }
        ans=min(abs(cnt[0]-cnt[1]),ans);
    }while (next_permutation(chk.begin(),chk.end()));
    cout << ans;
    return 0;
}