[백준/BOJ] 백준 14889번 : 스타트와 링크

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

팀이 나누어지는 모든 경우를 구하여 능력치 차이의 최솟값을 구한다. 팀이 나누어지는 경우는 next_permutation를 통해 구했다.

 

코드

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

int n;
int board[20][20];

int Solve()
{
	int ret = 987654321;
	int s_team;
	int l_team;
	vector<int> select(n, 0);

	//링크팀을 나타낼 수 (n/2)만큼 1을 표시한다
	for (int i = 0; i < n / 2; i++)
		select[i] = 1;

	//next_permutation 사용전 정렬
	sort(select.begin(), select.end());

	do {
		s_team = 0;
		l_team = 0;

		for (int i = 0; i < select.size(); i++)
		{
			//i번이 스타트팀일때
			if (select[i] == 0)
			{
				for (int j = 0; j < select.size(); j++)
				{
					if (select[j] == 0)
					{
						s_team += board[i][j];
					}
				}
			}

			//i번이 링크팀일때
			else if (select[i] == 1)
			{
				for (int j = 0; j < select.size(); j++)
				{
					if (select[j] == 1)
					{
						l_team += board[i][j];
					}
				}
			}
		}

		//능력치 차이의 최솟값을 구한다
		ret = min(ret, abs(s_team - l_team));

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

	return ret;
}

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

	int input;

	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			cin >> input;
			board[i][j] = input;
		}

	cout << Solve();

	return 0;
}