[C++/백준] 14889번: 스타트와 링크

문제 링크

14889번: 스타트와 링크

 

풀이

백트래킹 문제

1. 먼저 팀은 두 개로 나누어지기 때문에 한 쪽 팀을 구하면 자동으로 다른 팀이 만들어진다. 그래서 n명의 사람 중에 n/2의 사람만 뽑으면 됨.
2. 또한 순열이 아닌 조합이기 때문에 해당 팀에 그 사람이 있는지 확인하는 작업이 필요없이 바로 curIdx+1부터 뽑으면 된다.(왜냐면 그 전에 뽑힌 조합일 것이기 때문)
3. 그렇게 func 함수로 team의 사이즈가 n/2가 될 때까지 뽑고, 다 뽑히면 각 팀의 능력치를 계산한다.(calculate)
4. calculate 함수에서는, 0~n-1의 사람을 한 명씩 체크하면서, 다른 사람들을 체크한다.
   1. 해당하는 사람이 team에 있다면, 다른 선수도 그 team에 있어야 능력치를 더해주기 때문에 찾아주는 작업을 해준다.
   2. team에 있는 사람은 다른 선수도 그 team에 있는지, 아닌 사람은 없는지 체크해주는 것
   3. 그렇게 start와 link를 갱신해주고 둘이 뺀 값의 절댓값을 구해 answer의 최솟값을 갱신해주면 된다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 2001
using namespace std;

int answer = INF;

int calculate(vector<vector<int>> &v, vector<int> team, int n)
{
    int start = 0, link = 0;
    for (int i = 0; i < n; i++) // 선수 한명씩 체크
    {
        for (int j = 0; j < n; j++) // 다른 선수들과 같은 팀인지 확인
        {
            if (find(team.begin(), team.end(), i) != team.end()) // 선수가 팀에 있다면
            {
                if (find(team.begin(), team.end(), j) != team.end())
                {
                    start += v[i][j];
                }
            }
            else
            {
                if (find(team.begin(), team.end(), j) == team.end())
                {
                    link += v[i][j];
                }
            }
        }
    }

    return abs(start-link);
}

void func(vector<vector<int>> &v, vector<int> team, int curIdx)
{
    if (team.size() >= v.size() / 2)
    {
        answer = min(answer, calculate(v, team, v.size()));
        return;
    }

    for (int i = curIdx+1; i < v.size(); i++)
    {
        team.push_back(i);
        func(v, team, i);
        team.pop_back();
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<vector<int>> v(n, vector<int>(n));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> v[i][j];
        }
    }

    for (int i = 0; i < n; i++)
    {
        func(v, {i}, i);
    }
    cout << answer << endl;

    return 0;
}