백준 14889 (스타트와 링크)

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

14889번: 스타트와 링크

해당 문제는 총 n 명의 사람을 조합을 이용해 2개의 팀을 만들어 해당 팀의 평균 능력치를 구하여 각 팀 능력치의 절대값 중 최소값을 구하는 문제이다.

풀이 :

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;
int n;
int used[21];
int map[21][21];
int result = 999999;
vector<int> sList;
vector<int> lList;

// 각 팀 능력치의 평균 편차 구하기
int compTeam(vector<int> steam, vector<int> lteam){
	int sumS = 0;
	int sumL = 0;

	for (int i = 0; i < n / 2; ++i){
		for (int j = 0; j < n / 2; ++j){
			sumS += map[steam[i]][steam[j]];
			sumL += map[lteam[i]][lteam[j]];
		}
	}
	return abs(sumS - sumL);
}

void dfs(int level, int idx){
	if (level == n / 2){
		lList.clear();
        // S팀이 결정 되었을 때 포함되지 않은 인원을 L팀에 포함시킨다.
		for (int i = 1; i <= n; ++i){
			if (used[i] == 1) continue;
			lList.push_back(i);
		}
		int tmp = compTeam(sList, lList);
		if (tmp < result) result = tmp;
		return;
	}
	
    // S팀의 팀원 구하기
	for (int i = idx; i <= n; ++i){
		used[i] = 1;
		sList.push_back(i);
		dfs(level + 1, i + 1);
		used[i] = 0;
		sList.pop_back();
	}



}

int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> n;

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

	dfs(0, 1);
	cout << result << endl;

}