백준 14889. 스타트와 링크 (조합)

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

14889번: 스타트와 링크

조합으로 사람들을 두팀으로 나누고(nC(n/2)), 팀 별로 팀원 두명을 뽑아서((n/2)C2) 팀의 능력치를 계산하는 조합을 한번더 해준다. 

나는 이렇게 조합속에서 조합을 한번 더 했는데, 이렇게 하다보니 변수가 많아지고, 코드가 복잡해져서 터무니 없는 실수들을 했다. 

 

1. 특징

1) 조합속 조합: 내풀이에서는,,, 

 

2. 삽질 포인트

1) next_permutation으로 생성되는 배열을 잘못생각해서 오류가 발생했다. n = 8인 경우 팀원은 {1,2,3,4,5,6,7,8}이다. 

{1, 2, 3, 4} {5, 6, 7, 8}과 같이 두팀으로 나눠졌다고 가정하자.

이때 팀원간 능력치 계산을 위해 {1, 2, 3, 4}에서 두명을 next_permutation으로 뽑는 경우는 {1, 2} {1, 3} {1, 4} {2, 3} {2, 4} {3, 4}가 될 수 있다. 우리는 Sij 뿐아니라 Sji도 구해서 팀 능력치에 더해줘야하므로, {1,2}인 경우 sum += arr[1][2]; sum += arr[2][1];로 계산해주어야한다. 

 

3. 코드

#include <bits/stdc++.h>
using namespace std;

int n;
int arr[22][22];
int mn;
int mask[22];
int smask[22];
int lmask[22];
vector<int> _stavec;
vector<int> _linkvec;
int sta[2];
int lin[2];


int main()
{
    cin >> n;

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

    mn = INT_MAX;
    int hn = n / 2;

    for(int i = hn; i < n; i++)
    {
        mask[i] = 1;
    }
    int stasum = 0;
    int linksum = 0;
    do
    {
        _stavec.clear();
        _linkvec.clear();
        stasum = 0;
        linksum = 0;
        for(int i = 0; i < n; i++)
        {
            if(mask[i] == 0)
            {
                _stavec.push_back(i+1);
            }
            else
            {
                _linkvec.push_back(i+1);
            }
        }

        
        //_stavec에서 두개를 고르는 경우
        for(int i = 2; i < hn; i++) {smask[i] = 1;}
        //_linkvec 두개를 고르는 경우
        for(int i = 2; i < hn; i++) {lmask[i] = 1;}
        do
        {
            int cnt = 0;
            for(int i = 0; i < hn; i++)
            {
                if(smask[i] == 0)
                {
                    sta[cnt++] = _stavec[i]-1;
                
                }
            }
            stasum += arr[sta[0]][sta[1]];
            stasum += arr[sta[1]][sta[0]];

        }while(next_permutation(smask, smask + hn));

        do
        {
            int cnt = 0;
            for(int i = 0; i < hn; i++)
            {
                if(lmask[i] == 0)
                {
                    lin[cnt++] = _linkvec[i] -1 ;
                }
            }
            linksum += arr[lin[0]][lin[1]];
            linksum += arr[lin[1]][lin[0]];

        }while(next_permutation(lmask, lmask + hn));

        mn = min(mn, abs(linksum - stasum));

    }while(next_permutation(mask, mask+n));



    cout << mn;

}