[14889] 스타트와 링크

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

N명의 사람들이 스타트와 링크 팀으로 나누어 축구를 한다. (N은 2의 배수)

각 팀원들은 서로간의 시너지가 발생한다.

이것을 나타낸 능력치 표가 주어졌을 때

스타트 팀의 시너지 합과 링크 팀의 시너지 합이 최소가 되도록 했을 때

최소 값을 구하는 문제이다.

N이 최대 20이므로 완전 탐색을 이용하면 되고

백트레킹으로 N/2명씩 두 팀을 계속 선택해가며 최소 값을 비교하면 된다.

끝.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, arr[22][22], mini;
bool disc[22];
void func(int num, int r){
    if(num >= n-1){
        if(!r){
            int st=0, lt=0;
            for(int i=0; i<n; i++){
                if(disc[i]){
                    for(int j=0; j<n; j++){
                        if(disc[j]){
                            st += arr[i][j];
                        }
                    }
                }else{
                    for(int j=0; j<n; j++){
                        if(!disc[j]){
                            lt += arr[i][j];
                        }
                    }
                }
            }
            int diff = st>=lt?st-lt:lt-st;
            mini = min(mini, diff);
        }
        return ;
    }
    if(r>0){
        disc[num] = 1;
        func(num+1, r-1);
        disc[num] = 0;
    }
    func(num+1, r);
}
int main(){
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf("%d", &arr[i][j]);
        }
    }
    mini = 987654321;
    func(0, n/2);
    printf("%d\n", mini);
    return 0;
}