14889 스타트와 링크

조합을 이용하여 팀을 나눈다. 

Solution 

1. 조합을 이용해 팀을 나눈다
2. 팀별로 연산을 한다.

 

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<queue>
using namespace std;

#define INF 1000000000


int main(void) {

	freopen("inp.inp", "r", stdin);
	freopen("out.out", "w", stdout);

	vector<vector<int>> map;
	vector<int> person;
	int amount = 0;
	cin >> amount;
	for (int i = 0; i < amount; i++) {
		vector<int> a;
		map.push_back(a);
		person.push_back(i);
		for (int j = 0; j < amount; j++) {
			int box;
			cin >> box;
			map[i].push_back(box);
		}
	}
	vector<int> ind;
	int k = amount/2;
	for (int i = 0; i < k; i++) {
		ind.push_back(1);
	}
	for (int i = 0; i < k; i++) {
		ind.push_back(0);
	}
	int mins = INF;
	sort(ind.begin(), ind.end());
	do {
		int A = 0;
		int B = 0;
		vector<int> alist;
		vector<int> blist;
		for (int i = 0; i < ind.size(); i++) {
			if (ind[i] == 0)
				alist.push_back(i);
			else
				blist.push_back(i);
		}
		for (int i = 0; i < alist.size(); i++) {
			for (int j = i; j < alist.size(); j++) {
				A += map[alist[i]][alist[j]];
				A += map[alist[j]][alist[i]];
			}
		}
		for (int i = 0; i < blist.size(); i++) {
			for (int j = i; j < blist.size(); j++) {
				B += map[blist[i]][blist[j]];
				B += map[blist[j]][blist[i]];
			}
		}
		int box = A - B;
		if (box < 0)
			box = -box;
		if (mins >box) {
			mins = box;
		}
	} while (next_permutation(ind.begin(), ind.end()));
	cout << mins;
	return 0;
}

 

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크