[SWEA 4012] 요리사

출처 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

 

int N, result, total;

int map[16][16];

bool check[16];

 

int cal(vector<int> &v)

{

    int tmp = 0;

    for (int i = 0; i < total;i++) for (int j = 0; j < total; j++)

    {if (i == j) continue; tmp += map[v[i]][v[j]];}

    return tmp;

}

 

int sin()

{

    vector <int> a; vector <int> b;

    for (int i = 0; i < N; i++)

    {

        if (check[i]) a.push_back(i);

        else b.push_back(i);

    }

    return abs(cal(a) - cal(b));

}

 

void dfs(int wh, int cnt)

{

    if (cnt == total) { result = min(result, sin()); return; }

 

    for (int i = wh; i < N; i++) if (!check[i]) { check[i] = true; dfs(i, cnt + 1); check[i] = false; }

 

}

 

int main()

{

    int T; int tc = 1;

    cin >> T;

    while (T--)

    {  

        cin >> N;

        for (int i = 0;i < N;i++) for (int j = 0;j < N; j++) cin >> map[i][j];

        total = N / 2;  result = 2e9;

        check[0] = true; dfs(1, 1);

        cout <<"#" << tc++ << " " << result << endl;

    }

         

    return 0;

}