백준 14889번: 스타트와 링크 (C++)

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

순열과 조합을 적절히 사용해주면 되는 문제였다.

먼저 팀을 나누기 위해서는 순서는 중요하지 않기 때문에 조합으로 뽑는다.

0, 1, 2, 3, 4, 5 이렇게 6명의 사람이 있으면 조합으로 3개를 뽑아서 두 개의 팀을 만들어 준다.

이어서 팀 각각에 대해서 보자.

예를 들어 스타트 팀이 0, 1, 2로 결정되면 링크 팀은 자연스럽게 3, 4, 5로 결정된다.

이제 팀 각각에 대해서 점수를 계산해주면 된다.

S01과 S10이 다르다고 했다. 따라서 스타트팀의 경우에 대해서 순열로 뽑아준다. 총 3P2가지가 나올 것이다.

이를 더해서 점수 하나를 만들어주고, 링크팀에 대해서도 진행해준다. 이제 점수차이의 최솟값을 찾으면 된다.

점수 계산시 순열을 사용하지 않고, 조합으로 뽑은 이후에, 순서를 뒤집어서 계산을 추가해줘도 동일한 결과가 나온다. 하지만 순열로 처리하면 한 번에 처리할 수 있기 때문에 순열을 사용했다.

#include<iostream>
#include<vector>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n, m[21][21], st = 0, arr[11], sco[11]; //arr이 팀1, sco가 자리순열
vector<int> v; //팀2
 
bool isused[21], isused2[11];
int Sum = 0, Sum2 = 0, res = 200;
void cntScore(int k, int a[]) { //스타트팀에 대한 점수 계산, 순열로 한다.
    
    if (k == 2) {
    
        Sum += m[sco[0]][sco[1]];
        return;
    }
    for (int i = 0; i < n / 2; i++) {
        if (!isused2[i]) {
            sco[k] = a[i];
            isused2[i] = true;
            cntScore(k + 1, a);
            isused2[i] = false;
        }
    }
}
void cntScore2(int k) { // 링크팀에 대한 점수 계산, 순열로 한다.
    
    if (k == 2) {
        
        Sum2 += m[sco[0]][sco[1]];
        return;
    }
    for (int i = 0; i < n / 2; i++) {
        if (!isused2[i]) {
            sco[k] = v[i];
            isused2[i] = true;
            cntScore2(k + 1);
            isused2[i] = false;
        }
    }
}
void makeTeam(int k) { //팀 선택은 조합으로 한다.
    if (k == n / 2) {
 
        for (int i = 0; i < n; i++) //팀1에서 선택 안 된 애들이 팀2로
            if (!isused[i]) v.push_back(i);
        
        cntScore(0, arr); //팀1 점수 계산
        
        cntScore2(0); //팀2 점수 계산
        
        res = min(res, abs(Sum - Sum2));
        Sum = 0, Sum2 = 0;
        v.clear();
 
        return;
    }
 
    if (k == 0) st = 0;
    for (int i = st; i < n; i++) {
        if (!isused[i]) {
            arr[k] = i;
            st = i;
            isused[i] = true;
            makeTeam(k + 1);
            isused[i] = false;
        }
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin >> n;
 
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++)
            cin >> m[i][j];
    
    makeTeam(0);
    cout << res;
    return 0;
}