[백준 15661] 링크와 스타트 (C++)

문제 링크: https://www.acmicpc.net/problem/15661

15661번: 링크와 스타트

1. 주의할 점

- 한팀에는 최소 1명이 있을 수 있고, A팀과 B팀의 인원수는 같지 않아도 된다

- 현재 구현한 방법은 중복된 경우가 있기 때문에(X2) 시간이 2배로 든다

 

2. 구현

- 브루트포스를 통해 1명~N-1까지 팀을 이뤘을때 각 팀원들에 해당하는 능력치의 합을 구한다

- 브루트포스의 경우, Next_permutation 함수를 통해 구현한다

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
int arr[20][20];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int num, result = 987654321;
	cin >> num;
	for (int i = 0; i < num; i++)
		for (int j = 0; j < num; j++)
			cin >> arr[i][j];
	for (int t = 1; t < num - 1; t++) {
		vector<int> v;
		for (int i = 0; i < t; i++)
			v.push_back(0);
		for (int i = 0; i < num - t; i++)
			v.push_back(1);

		do {
			int a_sum = 0, b_sum = 0;
			vector<int> a, b;
			for (int i = 0; i < num; i++) {
				if (v[i] == 0) a.push_back(i);
				else b.push_back(i);
			}
			for (int i = 0; i < a.size()-1; i++) 
				for (int j = i + 1; j < a.size(); j++) 
					a_sum += (arr[a[i]][a[j]] + arr[a[j]][a[i]]);					
			for (int i = 0; i < b.size() - 1; i++) 
				for (int j = i + 1; j < b.size(); j++) 
					b_sum += (arr[b[i]][b[j]] + arr[b[j]][b[i]]);

			result = min(result, abs(a_sum - b_sum));
		} while (next_permutation(v.begin(), v.end()));
	}
	cout << result;
	system("pause");
	return 0;
}