[백준 c++] 14889 스타트와 링크

문제

https://www.acmicpc.net/problem/14889
N(4 ≤ N ≤ 20, N은 짝수)명을 두 팀으로 나눴을 때 각 팀의 능력치 차이의 최소값을 구하는 문제다.
능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

풀이

우선 팀을 나눠야하기 때문에 비트마스킹을 이용했다.
n명의 사람 가운데 비율 상관 없이 뽑는 경우의 수는 (2^n)-1

각 자리 수의 비트가 켜져있는지 체크해서 비트가 1이라면 team_a 벡터에 넣고 0이면 team_b 벡터에 넣는다.

ex) 
i = 10 = 1010

i&(1<<0) = 0 //왜냐면 0번째 비트가 0이라서
i&(1<<1) = 1 

for (int i = 1; i < (1 << n); i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i & (1 << j))
                team_a.push_back(j + 1);
            else
                team_b.push_back(j + 1);
        }

벡터의 크기가 n/2라면 각 팀이 절반씩 나뉜 것이므로 능력치 계산 함수를 실행한다.
각 함수가 끝나면 능력치 차이의 최소값을 계산한다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, a[21][21], cap_a, cap_b, res = 987654321;
vector<int> team_a, team_b;
void go()
{
    for (int i = 0; i < team_a.size(); i++)
    {
        int a1 = team_a[i], b1 = team_b[i];
        for (int j = 0; j < team_a.size(); j++)
        {
            int a2 = team_a[j], b2 = team_b[j];
            cap_a += a[a1][a2];
            cap_b += a[b1][b2];
        }
    }
    res = min(res, abs(cap_a - cap_b));
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];
    }

    for (int i = 1; i < (1 << n); i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i & (1 << j))
                team_a.push_back(j + 1);
            else
                team_b.push_back(j + 1);
        }
        if (team_a.size() == (n / 2))
            go();
        team_a.clear();
        team_b.clear();
        cap_a = 0;
        cap_b = 0;
    }
    cout << res << "\n";
}