14889번: 스타트와 링크
문제접근🤔
- start팀에서 뽑아간 선수를 check에 true로 표시
- 뽑은 선수의 수가 n/2이 이면 그때부터 check 벡터를 확인하면서 start팀과 link팀 구별
- 구별된 벡터에서 순회하면서 각각의 결과 계산
놓쳤던 부분😅
코드😁
2028 KB
112 ms
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int n;
int answer = 2147483647;
vector<bool> check;
vector<vector<int>> stat;
void dfs(int idx, int person)
{
if ((n / 2) == person)
{
vector<int> start;
vector<int> link;
int start_score = 0;
int link_score = 0;
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 = i + 1; j < n / 2; j++)
{
start_score += (stat[start[i]][start[j]] + stat[start[j]][start[i]]);
link_score += (stat[link[i]][link[j]] + stat[link[j]][link[i]]);
}
}
answer = min(answer, abs(start_score - link_score));
return ;
}
for (int i = idx; i < n; i++)
{
if (!check[i])
{
check[i] = true;
dfs(i + 1, person + 1);
check[i] = false;
}
}
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
check.resize(n);
stat.resize(n, vector<int>(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> stat[i][j];
dfs(0, 0);
cout << answer;
}