백준 14889 - 스타트와 링크
1 minute read
문제링크
문제설명
- 축구를 하기 위해 총 N 명의 사람이 모인다. (N은 항상 짝수)
- 팀을 스타트 팀과 링크 팀으로 나눈다.
- 사람에게 1번부터 N번까지 번호를 배정하고 능력치를 조사했다.
S[i][j]
는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치를 의미한다. S[i][j]
와 S[j][i]
는 다를 수 있다.
- 팀의 능력치는 팀에 속한 모든 쌍의 능력치
S[i][j]
의 합이다.
- 두 팀의 능력치가 최소가 되는 경우를 구하라
문제접근
- 재귀호출을 통해 두 팀으로 나뉘면 각 팀의 능력치를 계산하고 차이를 반환한다.
- 두 팀으로 나누는 모든 경우의 수를 찾아 능력치 차이의 최솟값을 찾는다.
구현
#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>
#include <climits>
#define MAX_N 21
#define START 0
#define LINK 1
using namespace std;
int N;
int table[MAX_N][MAX_N];
int teamStatus[MAX_N];
int getAbility(vector<int> team)
{
int ret = 0;
for (int i = 0; i < team.size() - 1; i++) {
for (int j = i + 1; j < team.size(); j++) {
ret += (table[team[i]][team[j]] + table[team[j]][team[i]]);
}
}
return ret;
}
int getDiff()
{
vector<int> teamStart, teamLink;
for (int i = 1; i <= N; i++) {
if (teamStatus[i] == START) teamStart.push_back(i);
else if (teamStatus[i] == LINK) teamLink.push_back(i);
}
return abs(getAbility(teamStart) - getAbility(teamLink));
}
int splitTeam(int v, int cnt)
{
if (cnt == N / 2) {
return getDiff();
}
int ret = INT_MAX;
for (int i = v; i <= N; i++) {
if (teamStatus[i] == LINK) continue;
teamStatus[i] = LINK;
ret = min(ret, splitTeam(i, cnt + 1));
teamStatus[i] = START;
}
return ret;
}
int main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> N;
for (int r = 1; r <= N; r++) {
for (int c = 1; c <= N; c++) {
cin >> table[r][c];
}
}
memset(teamStatus, 0, sizeof(teamStatus));
cout << splitTeam(1, 0) << endl;
}
Leave a comment