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

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

14889번: 스타트와 링크

문제 요약

팀원 간 조합에 대한 점수가 2차원 배열이 입력 주어질 때, 
구성원을 2팀으로 나누는 모든 경우에 대하여,
(각 팀의 총 점수)의 차가 최소가 될 때의 그 값을 출력

문제 해결

• 최소값을 구해야 하므로 팀을 구성할 수 있는 모든 경우의 수를 살펴보아야 한다.
• 팀원 간 조합을 모두 따져봐야하므로 백트래킹을 시도한다.
  사람의 수가 4~20의 짝수 이므로, 최대 20C2의 조합의 개수가 발생하고, 2차원 배열의 크기가 최대 400이므로 2초안에 풀 수 있을 것이다.
• score[i][j] != score[j][i] 인 것에 유의 한다.

#include <iostream>
#include <vector>


int min_val = INT_MAX;
int n;
int arr[20][20];

using namespace std;
void go(int start, int count, int* check){
    if(count == n/2){
        int s=0, l=0;
        vector<int> start;
        vector<int> link; 
        for(int i = 0; i < n; i++)
        {
            if(check[i]) 
                start.push_back(i);
            else 
                link.push_back(i);
        }

        for(int i = 0; i<n/2; i++){
            for(int j=0; j<n/2; j++){
                s += arr[start[i]][start[j]];
                l += arr[link[i]][link[j]];
            } 
        }

        int diff = s-l;
        if(diff<0) diff *= -1;

        if(diff < min_val) min_val = diff;
        return;
    }

    for(int i=start; i<n; i++){
        if (!check[i]){
            check[i] = 1;
            go(i, count+1, check);
            check[i] = 0;
        } 
    }
}

int main(){
    cin >> n;

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

    int check[n] = {0};
    go(0, 0, check);

    cout << min_val;
}

각 팀의 점수를 계산할 때, score[i][j] != score[j][i] 인 것과 score[i][i]=0 인 것에 유의하여 코드를 작성하였다.