스타트링크

#include<iostream> #include<fstream> #include<vector> #include<list> #include<algorithm> #include<cmath> using namespace std; int res; int map[21][21]; int calc(vector<int> t_a, int teamSize) { int a = 0, b = 0; vector<int> t_b; for (int i = 1; i <= teamSize; i++) { if (find(t_a.begin(), t_a.end(), i) == t_a.end()) { t_b.push_back(i); } } for (auto ex : t_a) { for (auto ey : t_a) { a += map[ex][ey]; } } for (auto ex : t_b) { for (auto ey : t_b) { b += map[ex][ey]; } } return abs(a - b); } void func(vector<int> v, int teamSize) { int lastMem = v.back(); if (v.size() == teamSize / 2) { res = min(res, calc(v, teamSize)); return; } for (int i = lastMem + 1; i <= teamSize; i++){ v.push_back(i); func(v, teamSize); v.pop_back(); } } int main() { ifstream in("in.txt"); int T; in >> T; for (int t = 1; t <= T; t++) { int size; res = 100000; in >> size; for (int i = 1; i <= size; i++) { for (int j = 1; j <= size; j++) { in >> map[i][j]; } } vector<int> team; team.push_back(1); func(team, size); cout << res << endl; } } 

2n명의 인원을 가장 최소의 실력차이가 나도록 팀을 나누는 문제

n이 작아서 그냥 완전 탐색으로 가도 됐다.

사실 1번 선수가 들어간 팀을 중심으로 정리하면 모든 경우의 수가 다 나와서 생각보다 함수 호출 횟수는 작았다.