[#14889] 스타트와 링크

#include <iostream>
#include <vector>
#include <limits.h>
#include <math.h>
 
using namespace std;
 
vector<vector<int>> power;
vector<bool> isContain;  //start팀에 포함됐는지 여부
 
int minVal = INT_MAX;
 
void findAnswer(int cnt, int start, const int n) {
    //start팀 고르기. 링크팀은 스타트팀 고르면 알아서 골라짐
    if (cnt == n/2) {  //다 골랐으면
        int startSum = 0;
        int linkSum = 0;
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j)
                    continue;
 
                if (isContain[i] && isContain[j])  //i,j가 모두 start 팀이면
                    startSum += power[i][j];
 
                else if (!isContain[i] && !isContain[j])  //i,j가 모두 link 팀이면
                    linkSum += power[i][j];
            }
        }
 
        int diff = abs(startSum - linkSum);
        if (minVal > diff)
            minVal = diff;
 
        return;
    }
 
    
    for (int i = start; i < n; i++) {
        isContain[i] = true;
        findAnswer(cnt + 1, i + 1, n);
        isContain[i] = false;
    }
}
 
int main() {
    int n;
    cin >> n;
 
    power = vector<vector<int>>(n, vector<int>(n));
    isContain = vector<bool>(n, false);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> power[i][j];
        }
    }
 
    findAnswer(0, 0, n);
 
    cout << minVal;
    return 0;
}

 

start팀을 고르면 link팀은 알아서 골라지므로 start만 고르면 된다

nCn/2 조합 문제 풀듯이