14889 스타트와 링크

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

<아이디어>

N/2 명씩 두팀을 만들기 위해 check vector로 true면 A팀, false면 B팀으로 정합니다.

팀을 이룰 때는 순서에 상관없이 선택합니다.

재귀적으로 팀을 선택한 뒤, 정지조건(N/2명을 골랐을 때)을 만족하면, 팀의 점수를 계산합니다.

점수 계산은 이중 for문으로 완전탐색합니다.

점수차의 최솟값을 계산하여 출력합니다.

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int sum = INT_MAX;
 
void choice(int n, int pos, vector<vector<int>>& v, vector<bool>& check, int k)
{
    if(pos==n/2)
    {
        int asum = 0, bsum = 0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i==j) continue;
                else if(check[i]==check[j])
                {
                    if(check[i]) asum += v[i][j];
                    else bsum += v[i][j];
                }
            }
        }
        sum = min(sum, abs(asum-bsum));
        return ;
    }
    for(int i=k;i<n;i++)
    {
        if(!check[i])
        {
            check[i] = true;
            choice(n, pos+1, v, check, i+1);
            check[i] = false;
        }
    }
 
}
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    vector<vector<int>> v(n, vector<int> (n, 0));
    vector<bool> check(n, false);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>v[i][j];
 
    choice(n, 0, v, check, 0);
    cout<<sum;
    
 
    return 0;
}