14889번 스타트와 링크

내가 봐도 너무 비효율적으로 짠 것같다.. 나는 순열이나 조합을 재귀로 직접 구현하는 것을 선호하는데, 풀이에서는 next_permutation으로 그냥 넘겨버리는 것 같다. 나중에 이번 문제보다 약간 더 어려운 "링크와 스타트"에서 보완해봐야겠다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
int map[21][21];
int ch[21];
int res = 2147000000;
int maxi = 0;
int maxi2 = 0;


void DFS(int s, int L) {
	
	if (L==n/2) {
		//if (ch[1] != 1) return;
		vector<int> first;
		vector<int> second;
		for (int i = 1; i <= n; i++) {
			if (ch[i] == 1) {
				//cout << i << " ";
				first.push_back(i);
			}
			else {
				//cout << i << " ";
				second.push_back(i);
			}
		}
		//cout << '\n';
		int sum1 = 0;
		int sum2 = 0;
		for (int i = 0; i < n/2;i++) {
			//cout << i << '\n';
			for (int j = 0; j < n / 2; j++) {
				if (i == j) continue;
				sum1 += map[first[i]][first[j]];
			}
			//cout << first[i]<<" ";
		}
		//cout << '\n';
		for (int i = 0; i < n / 2;i++) {
			for (int j = 0; j < n / 2; j++) {
				if (i == j) continue;
				sum2 += map[second[i]][second[j]];
			}
		}
		res = min(res, abs(sum1-sum2));
		//cout << res;
		//cout << '\n';
		

	}
	else {
		for (int i = s + 1; i <= n;i++) {
			if (ch[i]==0) {
				ch[i] = 1;
				DFS(i, L + 1);
				ch[i] = 0;
			}
		}
	}
}
int main() {
	//freopen("in1.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];
		}
	}
	DFS(0, 0);
	cout << res << '\n';
	return 0;
}