스타트와 링크

코드

#include <iostream> 
#include <algorithm> 
#include <vector> 
#include <deque>
#include <map>
#include <cmath>
using namespace std;
int board[25][25];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, ans=1e9;
    cin >> N;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            cin >> board[i][j];
    int ch[N];
    fill(ch, ch+N, 1);
    for(int i=0;i<N/2;i++) ch[i] = 0;

    do{
        vector<int> start;
        vector<int> link;
        for(int i=0;i<N;i++)
        {
            if(ch[i] == 0)
                start.push_back(i);
            else
                link.push_back(i);
        }
        int start_sum = 0;
        int link_sum = 0;
        for(int i=0;i<N/2;i++)
        {
            for(int j=0;j<N/2;j++)
            {
                if(i == j) continue;
                start_sum += board[start[i]][start[j]];
                link_sum += board[link[i]][link[j]];
            }
        }
        ans = min(ans, (int)abs(start_sum - link_sum));
    }while(next_permutation(ch, ch+N));
    cout << ans;
    return 0;
}

• 로직
  : N명의 사람들을 절반으로 나누는 모든 조합을 next_permutaion()으로 구하고 합의 최소를 찾는다