14889번-스타트와 링크

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n;	//총 n 명. n을 반반씩 나눠서 팀을 나눈다. 

int board[25][25];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
		}
	}
	vector<int> team(n);
	fill(team.begin() + (n / 2), team.end() , 1);
	int mn = 0x7f7f7f7f;
	do {
		int diff = 0;
		for (int i = 0; i < n-1; i++) {
			for (int j = i + 1; j < n; j++) {
				if (team[i] != team[j])continue;
				if (team[i] == 0)diff += (board[i][j] + board[j][i]);
				else diff -= (board[i][j] + board[j][i]);
			}
		}
		mn = min(mn, abs(diff));
	} while (next_permutation(team.begin(),team.end()));
	cout << mn;
}

next_permutation은 내부 동작으로

현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 true 반환

다음 순열이 없다면 (= 다음에 나온 순열이 순서상 이전 순열보다 작다면) false 반환.

즉, 이전 수보다 작은 것은 나오지 않는다. 

따라서 next_permutation을 위한 조합을 구할 때는 1을 뒤에 오는 배열을 만들어서 돌려야한다.