스타트와 링크

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

int s[20][20];
int n;
int go(int index, vector<int>& a, vector<int>& b) {
	if (index == n) {
		if (a.size() != n / 2) return -1;
		if (b.size() != n / 2) return -1;
		int t1 = 0;
		int t2 = 0;
		for (int i = 0; i < n / 2; i++) {
			for (int j = 0; j < n / 2; j++) {
				if (i == j) continue;
				t1 += s[a[i]][a[j]];
				t2 += s[b[i]][b[j]];
			}
		}
		int diff = t1 - t2;
		if (diff < 0) diff = -diff;
		return diff;
	}
	if (a.size() > n / 2) return -1;
	if (b.size() > n / 2) return -1;
	int ans = -1;
	a.push_back(index);
	int t1 = go(index + 1, a, b);
	if (ans == -1 || (t1 != -1 && ans > t1)) {
		ans = t1;
	}
	a.pop_back();
	b.push_back(index);
	int t2 = go(index + 1, a, b);
	if (ans == -1 || (t2 != -1 && ans > t2)) {
		ans = t2;
	}
	b.pop_back();
	return ans;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> s[i][j];
		}
	}
	vector<int> a,b;
	cout << go(0, a, b) << "\n";
	return 0;

}

백트래킹 해서 문제풀기

재귀함수 잘못썼을때는 그냥 순열써서 풀었던기억이난다.

시간이 매우매우 많이 단축됨을확인할수있음