백준 14889번 스타트와 링크

문제 링크 : https://www.acmicpc.net/problem/14889

문제 접근

1. 재귀를 통해 팀이 이루어지는 모든 경우의 수를 완전탐색하였다.

2. 각 경우당 팀별 능력치의 합을 구하여 두 팀간의 능력치합의 차를 구하였고 그중 가장 작은 값을 출력하였다.

소스코드

#include <iostream>
#include <vector>
 
using namespace std;
 
int n, halfN, minans = 99999;
int s[50][50];
bool selectN[50];
 
vector <int> trueTeam;
vector <int> falseTeam;
 
void recur(int minimumNum, int toPick) {
    if (toPick == 0) {
 
        trueTeam.clear();
        falseTeam.clear();
 
        // 처리
        for (int i = 0; i < n; i++) {
            if (selectN[i] == true)
                trueTeam.push_back(i);
            else
                falseTeam.push_back(i);
        }
        
        int ttsum=0, ftsum=0;
 
        for (int i = 0; i < trueTeam.size(); i++) {
            for (int j = 0; j < trueTeam.size(); j++) {
                if (i == j) continue;
 
                ttsum += s[trueTeam[i]][trueTeam[j]];
 
            }
        }
 
        for (int i = 0; i < falseTeam.size(); i++) {
            for (int j = 0; j < falseTeam.size(); j++) {
                if (i == j) continue;
 
                ftsum += s[falseTeam[i]][falseTeam[j]];
            }
        }
 
        int chai = ttsum > ftsum ? ttsum - ftsum : ftsum - ttsum;
 
        if (minans > chai)
            minans = chai;
 
        return;
    }
 
    for (int i = minimumNum; i < n; i++) {
        selectN[i] = true;
        recur(i + 1, toPick - 1);
        selectN[i] = false;
    }
 
}
 
int main()
{
    cin >> n;
    halfN = n / 2;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> s[i][j];
    
    recur(0, halfN);
 
    cout << minans;
 
}