스타트와 링크

문제 링크

이 문제도 이전 문제들과 비슷하지만 두가지 차이점이 있다.

1. 사람을 뽑을 때 순서를 고려하지 않는다. ( 합은 순서와 상관이 없으므로 )
2. N / 2 명의 사람을 뽑고 나면 나머지는 자동으로 정해진다. 이전 문제에서는 같은 숫자를 뽑더라도 순서를 다르게 뽑으면 다른 순열로 취급했기 때문에 코드 작성이 용이했지만, 이제 순서를 고려하지 않으므로 새로운 제약을 추가해야 한다. 바로 순서를 오름차순으로 강제하는 것이다. ( 내림차순도 당연히 상관 없다. 이 외에도 특정한 규칙으로 정렬만 가능하면 된다. ) 오름차순으로만 순회하면 같은 숫자 조합을 2번 이상 방문할 수 없다. N 은 항상 짝수이므로 N / 2 명의 사람을 정하고 양 측의 능력치 합의 차의 최소값을 구한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n; vector<vector<int>> arr;
vector<int> res;
int dm = 21e8;
void r(int p) {
	if (p > n / 2) {
		int s1 = 0; int s2 = 0;
		vector<int> r1, r2, ch(n + 1);
		for (int i = 1; i <= n / 2; i++) {
			ch[res[i]] = 1;
		}
		for (int i = 1; i <= n; i++) {
			ch[i] == 1 ? r1.push_back(i) : r2.push_back(i);
		}		
		for (int i = 1; i <= n / 2; i++) {
			for (int j = i + 1; j <= n / 2; j++) {				
				s1 += arr[r1[i - 1]][r1[j - 1]];
				s1 += arr[r1[j - 1]][r1[i - 1]];
				s2 += arr[r2[i - 1]][r2[j - 1]];
				s2 += arr[r2[j - 1]][r2[i - 1]];
			}
		}
		dm = dm < abs(s1 - s2) ? dm : abs(s1 - s2);
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (p > 1 && res[p - 1] >= i) continue; // 번호 순서를 오름차순으로 강제하기
		res[p] = i;
		r(p + 1);		
	}
}
int main() {
	cin >> n; arr = vector<vector<int>>(n + 1, vector<int>(n + 1)); res = vector<int>(n / 2 + 1);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
		}
	}
	r(1);
	cout << dm;
	return 0;
}