[백준 14889] 스타트와 링크

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

14889번: 스타트와 링크

요구사항

1. 팀 시너지의 차가 최소가 되는 값 구하기

 

풀이

1.  2개의 팀으로 나눈다

2. 각 각의 합을 구한다

3. 합의 최소를 구한다.

 

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

using namespace std;
int n;
int map[21][21];
int visit[21];
int ans = 987654321;
void com(int arr[], int n, int r, int now, int pos) {
	if (r == now) {
		//계산
		int tempsum1 = 0;
		int tempsum0 = 0;
		int tempans = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j)
					continue;
				if (visit[i] == 1 && visit[j] == 1) {
					tempsum1 += map[i][j];
				}
				if (visit[i] == 0 && visit[j] == 0) {
					tempsum0 += map[i][j];
				}
			}
		}
		tempans = abs(tempsum1 - tempsum0);
		ans = min(tempans, ans);
		return;
	}
	for (int i = pos; i < n; i++) {
		if (visit[i] == 1) continue;
		visit[i] = 1;
		com(arr, n, r, now + 1, i);
		visit[i] = 0;

	}
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	com(visit, n, n / 2, 0, 0);
	cout << ans << endl;
	
}