[SW Expert Academy] - 요리사

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

int n,ans;
int map[21][21];
int chk[21];

void dfs(int idx,int size){
    if(size == n / 2 ){
        int temp1 = 0 , temp2 = 0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if( chk[i] && chk[j])
                    temp1 += map[i][j];
                else if ( !chk[i] && !chk[j])
                    temp2 += map[i][j];
            } // end of for j
        } // end of for i
        ans = ans > abs(temp1 - temp2) ? abs(temp1 - temp2) : ans;
    } // end of if
    else{
        for(int i=idx; i<=n; i++){
            chk[i] = 1;
            dfs(i+1, size+1);
            chk[i] = 0;
        }
    } // end of else
}
int main(){
    int TC;
    cin >> TC;
    for (int tc=1; tc<=TC; tc++) {
        cin >> n;
        ans = 2e9;
        memset(map,0,sizeof(map));
        memset(chk,0,sizeof(chk));
        
        for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) scanf("%d",&map[i][j]);
        dfs(1,0);
        
        printf("#%d %d\n",tc, ans);
    } // end of for tc
    
    return 0;
}

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;

int map[16][16];
int visit[16];
int ans,n;

int dfs(int idx, int cnt){
    if( cnt == n>>1){
        vector<int> v[2];
        for(int i=0; i<n; i++){
            if(visit[i]) v[1].push_back(i); else v[0].push_back(i);
        } // for i Loop
        
        int sum1, sum2;
        sum1 = sum2 = 0;
        
        for (int i = 0; i < n/2; i++) {
            for (int j = 0; j < n/2; j++) {
                if (i == j)continue;
                sum1 += map[v[0][i]][v[0][j]];
                sum2 += map[v[1][i]][v[1][j]];
            }
        }
        
        sum1 = abs(sum1-sum2);
        return sum1 > ans ? ans : sum1;
    }
    for(int i=idx; i<n; i++){
        visit[i] = 1 ;
        ans = min(ans, dfs(i+1,cnt+1));
        visit[i] = 0 ;
    }
    return ans;
}


int main(){
    int TC;
    cin >> TC;
    
    for(int tc=1; tc<=TC; tc++){
        memset(map,0,sizeof(map));
        memset(visit,0,sizeof(visit));
        ans = 2e9;
        
        cin >> n;
        for(int i=0; i<n; i++) for(int j=0; j<n; j++) scanf("%d",&map[i][j]);
        
        ans = min(dfs(0,0),ans);

        printf("#%d %d\n",tc,ans);
    }
    return 0;
}

// Before
    for(int i=0; i<(n >> 1) -1; i++){
        sum1 += map[ v[0][i] ][ v[0][i+1] ] + map[ v[0][i+1] ][ v[0][i] ];
        sum2 += map[ v[1][i] ][ v[1][i+1] ] + map[ v[1][i+1] ][ v[1][i] ];
    }

 // After
    for (int i = 0; i < n/2; i++) {
        for (int j = 0; j < n/2; j++) {
            if (i == j)continue;
            sum1 += map[v[0][i]][v[0][j]];
            sum2 += map[v[1][i]][v[1][j]];
        }
    }