[swea 4012] 요리사

분류 

dfs

요구사항

요리 조합의 합이 최소로 되게 팀짜기

풀이

1. dfs로 팀을 나눈다

0팀 반, 1팀 반

2. 같은 팀끼리의 합을 구할 수 있도록 한다

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
int n;
int map[20][20];
int visit[20];
int ans = 987654321;
void dfs(int cnt, int now) {

	if (now == n) {
		if (cnt == n / 2) {
			int nowsum[2] = { 0, };
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (i == j) continue;
					if (visit[i] == visit[j]) {
						nowsum[visit[i]] += map[i][j];
					}
				}
			}
			int diff = abs(nowsum[0] - nowsum[1]);
			ans = min(ans, diff);
		}
		return;
	}
	visit[now] = 1;
	dfs(cnt + 1, now + 1);
	visit[now] = 0;
	dfs(cnt, now + 1);
}
int main() {
	int t;
	scanf("%d", &t);
	for (int tc = 1; tc <= t; tc++) {
		ans = 987654321;
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				scanf("%d", &map[i][j]);
			}
		}
		dfs(0, 0);
		printf("#%d %d\n", tc, ans);
	}
}