[백준] 14889 스타트와 링크

14889번: 스타트와 링크

 

www.acmicpc.net

풀이

백트래킹 문제이다. 무작위로 팀을 선정해서 전체 인원 수 / 2 만큼의 인원을 고르면 나머지는 B팀으로 생각하고 능력치를 계산해서 최소값을 구하면 된다.

코드

#include <iostream>
#include <algorithm>
using namespace std;

int n, ans = 987654321;
int s[21][21];
bool a[21];

int get_result() {
    int sa = 0;    int sb = 0;    
    for(int i=1; i<=n-1; i++)
        for (int j = i + 1; j <= n; j++) {
            if (a[i] && a[j]) sa += s[i][j] + s[j][i];
            if (!a[i] && !a[j]) sb += s[i][j] + s[j][i];
        }
    return abs(sa - sb);
}

void dfs(int idx, int cnt) {
    if (cnt == n / 2) {
        ans = min(ans, get_result());
        return;
    }

    // 현재 인덱스 다음부터 선택한다
    for (int i = idx + 1; i <= n; i++) {
        a[i] = true;
        dfs(i, cnt + 1);
        a[i] = false;
    }
}

int main() { 
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> s[i][j];
    dfs(0, 0);
    cout << ans << '\n';
    return 0;
}