문제링크
축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다. 축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.
idx
번째 사람을 스타트팀에 넣는 경우 or 링크팀에 넣는 경우 각각 구분해서 재귀를 돌리는 방법이다.<algorithm>
헤더의 next_permutation()
함수를 사용하는데, 순열 조합은 거의 알고리즘이므로 사용할 때는 최대한 신경을 많이 써줘야 한다.1, 2 | 3, 4
이렇게 팀을 맺는것과 2, 1 | 3, 4
는 같은 결과다. 나열해보면, 4명에서 나올 수 있는 순열은 4! = 24가지지만, 유효한 조합은 1, 2 | 3, 4
, 1, 3 | 2, 4
, 1, 4 | 2, 3
이렇게 3가지 뿐이다. 따라서 첫 번째 숫자를 고정시켜버리고 n - 1
개 숫자에 대해서만 조합을 신경써주면 된다. 이러면 계산효율이 n배 증가하므로 매우매우 좋은 착안점이다. #include <iostream>
#include <vector>
using namespace std;
int N;
int stat[20][20];
vector<int> teamStart, teamLink;
int solve(int idx) {
// 백트래킹 사용: 재귀를 돌다가 불가능한 경우를 만날 경우 해당 재귀를 멈춘다.
if (teamStart.size() > N / 2 || teamLink.size() > N / 2) return -1;
if (idx == N) { // 모든 사람을 각 팀에 배분했다.
int statSumOfStart = 0, statSumOfLink = 0;
for (int i = 0; i < N / 2; ++i) {
for (int j = 0; j < N / 2; ++j) {
if (i == j) continue;
statSumOfStart += stat[teamStart[i]][teamStart[j]];
statSumOfLink += stat[teamLink[i]][teamLink[j]];
}
}
return abs(statSumOfStart - statSumOfLink);
}
int ret = -1, temp = -1;
// idx번째 선수를 'Start팀'에 넣는 경우
teamStart.push_back(idx);
temp = solve(idx + 1);
if (ret == -1 || (temp != -1 && ret > temp)) ret = temp;
teamStart.pop_back();
// idx번째 선수를 'Link팀'에 넣는 경우
teamLink.push_back(idx);
temp = solve(idx + 1);
if (ret == -1 || (temp != -1 && ret > temp)) ret = temp;
teamLink.pop_back();
return ret;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> N;
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
cin >> stat[i][j];
cout << solve(0) << '\n';
}
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
int score[n][n];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
cin >> score[i][j];
int ans = 1e9;
char check[n];
// The number of people in each team can be from 1 to n-1.
for (int part = 1; part <= n - 1; ++part) {
// initialize check array for permutation(or selection).
for (int i = 0; i < part; ++i) check[i] = 0;
for (int i = part; i < n; ++i) check[i] = 1;
int counterPart = n - part;
int teamS[part], teamL[counterPart];
do {
// devide team by permutation.
for (int i = 0, l = 0, r = 0; i < n; ++i)
(check[i]) ? teamL[r++] = i : teamS[l++] = i;
// get score sum of each team.
int sumS = 0, sumL = 0;
for (int i = 0; i < part; ++i)
for (int j = i + 1; j < part; ++j)
sumS += score[teamS[i]][teamS[j]] + score[teamS[j]][teamS[i]];
for (int i = 0; i < counterPart; ++i)
for (int j = i + 1; j < counterPart; ++j)
sumL += score[teamL[i]][teamL[j]] + score[teamL[j]][teamL[i]];
ans = min(ans, abs(sumS - sumL));
} while(next_permutation(check + 1, check + n)); // for increase calc speed!
}
cout << ans << '\n';
}