[C++] 삼성 4012. [모의 SW 역량테스트] 요리사

(30분) 재료를 분배하는 과정을 더 깔끔하게 짜고 싶은데 아이디어가 떠오르지 않음..

 

#include<iostream>
#include<vector>
#include<stdlib.h>
using namespace std;
 
int synergy[16][16];
int minDifference;
 
int calSynergy(vector<int> food){
    int totalSynergy = 0;
    for(int i=0; i<food.size(); i++){
        for(int j=0; j<food.size(); j++){
            totalSynergy += synergy[food[i]][food[j]];
        }
    }
    return totalSynergy;
}
 
void shareIndex(vector<int> A, vector<int> B, int N, int currentIndex){
    if(currentIndex == N){
        int difference = abs(calSynergy(A) - calSynergy(B));
        if(minDifference > difference)
            minDifference = difference;
        return;
    }
    
    if(A.size() < N/2){
        A.push_back(currentIndex);
        shareIndex(A, B, N, currentIndex + 1);
        A.pop_back();
    }
    
    if(B.size() < N/2){
        B.push_back(currentIndex);
        shareIndex(A, B, N, currentIndex + 1);
        B.pop_back();
    }
}
 
int main(){
    int T;
    cin >> T;
    for(int t=1; t<=T; t++){
        int N;
        cin >> N;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                cin >> synergy[i][j];
            }
        }
        
        minDifference = 9999999;
        vector<int> A;
        vector<int> B;
        shareIndex(A, B, N, 0);
        cout << "#" << t << " " << minDifference << endl;
    }
    
    return 0;
}