[Algorithm] Baekjoon 14889번 : 스타트와 링크

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

int n;
int arr[20][20] = { 0 };
int maxDepth;
vector<int> curNums;
int answer = 0x3f3f3f3f;
 
int CalcScoreGap()
{
    bool visited[20] = { false };
    int firstTeamScroe = 0;
    int secondTeamScore = 0;
 
    for (int i = 0; i < curNums.size(); ++i)
    {
        visited[curNums[i]] = true;
        for (int j = i + 1; j < curNums.size(); ++j)
        {
            firstTeamScroe += arr[curNums[i]][curNums[j]] + arr[curNums[j]][curNums[i]];
        }
    }
 
    for (int i = 0; i < n; ++i)
    {
        if (visited[i]) continue;
        for (int j = i + 1; j < n; ++j)
        {
            if (visited[j]) continue;
            secondTeamScore += arr[i][j] + arr[j][i];
        }
    }
 
    return abs(firstTeamScroe - secondTeamScore);
}
 
void DFS(int index)
{
    if (curNums.size() == maxDepth)
    {
        // 점수계산.
        if (curNums[0] == 0 && curNums[1] == 3)
        {
            int asfd = 0;
        }
        answer = min(answer, CalcScoreGap());
        return;
    }
 
    for (int i = index + 1; i < n; ++i)
    {
        curNums.push_back(i);
        DFS(i);
        curNums.pop_back();
    }
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
    maxDepth = n / 2;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    for (int i = 0; i < maxDepth + 1; ++i)
    {
        curNums.push_back(i);
        DFS(i);
        curNums.pop_back();
    }
 
    cout << answer;
}

각팀을 짰을 때 점수차이를 최소화해야한다.

그냥 각 선수를 뽑아서 팀을 구성했을 때마다 점수차이를 구하는 완전탐색으로 풀었다.