14889 스타트와 링크

BOJ::14889 스타트와 링크

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

N명의 사람을 두팀으로 나누고, 두팀 능력치 차의 최소값을 구하는 문제이다.

나는 백트래킹을 이용해 2팀으로 나누는 모든 경우에 대해 능력치 차의 최소값을 구하는 방법으로 풀었다.

#include <stdio.h>
#include <vector>
#include <math.h>
using namespace std;
#define INF 987654321
 
int n, cnt, res;
int map[20][20];
bool visited[20];
 
//팀의 능력치 합 구하기
int getStat(vector<int> v) {
    int m = v.size();
    int sum = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            sum += map[v.at(i)][v.at(j)];
        }
    }
    return sum;
}
 
//팀의 능력치 차이 계산하기
void calc() {
    vector<int> teamA;
    vector<int> teamB;
 
    for (int i = 0; i < n; i++) {
        if (visited[i]) {
            teamA.push_back(i);
        }
        else {
            teamB.push_back(i);
        }
    }
 
    int a = getStat(teamA);
    int b = getStat(teamB);
 
    if (abs(a-b) < res) {
        res = abs(a-b);
    }
}
 
//2개의 팀으로 나누는 모든 경우에대해 백트래킹
void dfs(int v) {
    cnt++;
    visited[v] = true;
 
    if (cnt == n / 2) {
        calc();
    }
    else {
        for (int i = v + 1; i < n; i++) {
            if (!visited[i]) {
                dfs(i);
            }
        }
    }
 
    cnt--;
    visited[v] = false;
}
 
int main() {
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &map[i][j]);
        }
    }
 
    res = INF;
    dfs(0);
 
    printf("%d\n", res);
}