14889 Samsung sw test

์ฝ”๋“œ

#include <iostream>
#include <cstring>
#define MAX_WIDTH 20
 
using namespace std;
 
int numOfPeople;
int map[MAX_WIDTH][MAX_WIDTH];
 
int minDifferenceBetweenTwoTeam(int arr[10], int len, int deep);
int getSum(int arr[10]);
int min(int a, int b);
 
int main() {
	cin >> numOfPeople;
	for (int i = 0; i < numOfPeople; i++)
		for (int j = 0; j < numOfPeople; j++)
			cin >> map[i][j];
 
	int arr[10];
	memset(arr, -1, sizeof(arr));
	cout << minDifferenceBetweenTwoTeam(arr, 0, 0);
}
 
int minDifferenceBetweenTwoTeam(int arr[10], int len, int deep) {
	if (len == numOfPeople / 2) {
		//๊ณ„์‚ฐ
		int temp[10];
		int index = 0;
		int indext = 0;
		for (int i = 0; i < numOfPeople; i++) {
			if (arr[index] == i)
				index++;
			else
				temp[indext++] = i;
		}
		int d = getSum(temp) - getSum(arr);
		return d < 0 ? (-1) * d : d;
	}
	else if (numOfPeople - deep < numOfPeople / 2 - len)
		return 10000000;
 
	arr[len] = deep;
	int a = minDifferenceBetweenTwoTeam(arr, len + 1, deep + 1);
	arr[len] = 0;
	return min(a, minDifferenceBetweenTwoTeam(arr, len, deep + 1));
}
 
int min(int a, int b) {
	return a < b ? a : b;
}
 
int getSum(int arr[10]) {
	int sum = 0;
	for (int i = 0; i < numOfPeople/2; i++)
		for (int j = 0; j < numOfPeople/2; j++)
			sum += map[arr[i]][arr[j]];
 
	return sum;
}