백준 14889 스타트와 링크

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

14889번: 스타트와 링크

총인원은 최대 20명이고(짝수만가능) 스타트팀, 링크팀 구성은 동일하게 구성된다.

각 멤버들이 같은팀일경우 해당되는 능력치가 2차원 배열로 주어지며 공정한 경기를 위해 두팀간의 능력치의 차이가 최소가 되도록 팀을 구성해야 한다. 그리고 그 최소값을 출력해야 한다.

 

따져야 하는 경우의 수는 모두 몇가지 일까?

이것은 중복 집한 순열의 개수를 구하는 것과 같다.

예를 들어 집합 { 1,2,3,4,5,6 } 으로 가능한 모든 순열의 개수는 6! 이다. 
그러나 만약 집합에 중복이 있다면 { 1,1,2,3,4,5 } 라면 가능한 모든 순열의 개수는 분명한것은 6! 보다 작다.

결과는 6! / 2! 이다. 1,1 은 서로 순서를 바꾸어도 동일하기 때문이다.

만약 { 0,0,0,1,1,1 } 이라는 집합의 모든 순열의 개수는 어떻게 될까

결과는 6! / ( 3! * 3! ) 이다. 자세한 내용은 아래 위키백과에 잘 설명되어 있다.

 

https://ko.wikipedia.org/wiki/%EC%88%9C%EC%97%B4

순열 - 위키백과, 우리 모두의 백과사전

 

따라서 본 문제는 20명을 10명으로 나누기때문에 집합은 { 0,0,0 .... 1,1,1} 이며 가능한 모든 조합의 개수는 20! / (10! * 10! ) 이되고 충분히 부르트 포스로 풀이할 수 있다.

인원수에 따라 각각 절반의 0 과 1로 구성된 집합을 만들고 그 집합의 모든 가능한 순열을 조합하면서 팀별 능력치를 구하고 그 차이가 최소인 값을 업데이트하면 된다.

 

#include <climits>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int abi[20][20];

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> abi[i][j];
	vector<int> teamMember;
	for (int i = 0; i < (n>>1); i++)
		teamMember.push_back(0);
	for (int i = 0; i < (n >> 1); i++)
		teamMember.push_back(1);

	int result = INT_MAX;
	do
	{
		int resultA = 0;
		int resultB = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (teamMember[i] == 0 && teamMember[j] == 0)
					resultA += abi[i][j];
				if (teamMember[i] == 1 && teamMember[j] == 1)
					resultB += abi[i][j];

			}
		}
		result = min(result, abs(resultA - resultB));

	} while (next_permutation(teamMember.begin(), teamMember.end()));

	cout << result << endl;
}