4012 요리사

1. 백트래킹을 통해  n/2 개 고르는 모든 경우에 대해 탐색한다.

2. n/2 개 고를때마다 시너지값을 구해 차를 구한다.

3. 반복하여 최소값을 찾는다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int t, n, res;
int map[16][16];
bool visited[16];
 
// 시너지 계산하기
int calc(vector<int> &v) {
    int ans = 0;
    for (int i = 0; i < n/2; i++) {
        for (int j = 0; j < n/2; j++) {
            if (i == j)continue;
            ans += map[v[i]][v[j]];
        }
    }
    return ans;
}
 
int getResult() {
    vector<int> a; // 선택된 팀
    vector<int> b; // 선택되지 않은 팀
 
    for (int i = 0; i < n; i++) {
        if (visited[i]) a.push_back(i);
        else b.push_back(i);
    }
    //시너지의 차 구하기
    return abs(calc(a) - calc(b));
}
 
//백트래킹
void dfs(int v, int cnt) {
    visited[v] = true;
 
    if (cnt == n/2) {
        res = min(res, getResult());
    }
    else {
        for (int i = v + 1; i < n; i++) {
            dfs(i, cnt + 1);
        }
    }
 
    visited[v] = false;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin >> t;
    
    for (int tc = 1; tc <= t; tc++) {
        cin >> n;
        res = 1e9;
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> map[i][j];
            }
        }
 
        dfs(0, 1);
 
        cout << "#" << tc << " " << res << "\n";
    }
}