요리사_4012

문제 출처 : 요리사_4012

#스타트와링크 문제랑 똑같음

파라미터 정리

T 테스트 케이스 개수 (1~50)
N 음식 개수 (N은 짝수) (4~16)
Sij 음식 간 시너지 (1~20000)
i == j 일 경우 시너지가 없음
팀의 총 시너지 = 각 재료 사이의 시너지 모두 더한 것
원하는 것 = 두 팀 사이의 식재료 시너지의 차이가 최소가 될 때 최솟값을 반환

간략한 과정

input_1 T 입력받기
input_2_1 N 입력받기
input_2_2 시너지 정보 Arr[16][16] 입력받기
비트 마스크 이용해서 경우의 수 만들기
비트 수가 딱 절반이 되었을 때
0은 A팀 1은 B팀으로 배정한다.
A,B 팀의 총 시너지 차이(sub)을 구한다.
res = min(res, sub)
output "#n" + res 출력하기

코드

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

using namespace std;

#define INF 984561542

int T,N;
int Arr[16][16];
vector<int> group_A;
vector<int> group_B;

int calculate(){
    //두 팀의 시너지 각각 계산하고 차이 반환
    int sum_A = 0, sum_B = 0;
    
    int size = group_A.size();
    for(int i = 0; i < size; i++){
        for(int j = i+1; j < size; j++){
            if(i==j) continue;
            int num1 = group_A[i], num2 = group_A[j];
            sum_A += Arr[num1][num2] + Arr[num2][num1];
        }
    }
    size = group_B.size();
    for(int i = 0; i < size; i++){
        for(int j = i+1; j < size; j++){
            if(i==j) continue;
            int num1 = group_B[i], num2 = group_B[j];
            sum_B += Arr[num1][num2] + Arr[num2][num1];
        }
    }
    
    return abs(sum_A-sum_B);
}

int checkBit(int n){
    int res = 0;
    do{
        if(n & 1) res++;
        n = n >> 1;
    }while(n>0);
    return res;
}

int solve(){
    int res = INF;
    for(int i = 0; i < (1 << N-1); i++){
        if(checkBit(i) == N/2){
            group_A.clear();
            group_B.clear();
            for(int j = 0; j < N-1; j++){
                if(i & (1<<j))  group_A.push_back(j);
                else group_B.push_back(j);
            }group_B.push_back(N-1);
            res = min(res,calculate());
        }
    }
    
    return res;
}

int main()
{
    cin >> T;
    for(int t = 0; t < T; t++){
        
        cin >> N;
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                cin >> Arr[i][j];
                
        cout << "#" << t+1 << " " << solve() << endl;
    }

    return 0;
}