<< 문제 >>
https://www.acmicpc.net/problem/14889
이것도 next_permutation()을 이용하면 쉽게 활용할 수 있다.
vector에 사람 수의 절반만큼 0, 또 절반만큼 1을 넣고 next_permutation을 돌리면 모든 경우의 팀 선정을 볼 수 있다.
이를 이용해서 모든 조합을 다 더해보면 알 수 있다.
<< 코드 >>
#include <iostream>
#include<vector>
#include <algorithm>
using namespace std;
int main() {
int num;
cin >> num;
// 둘이 합쳐진 능력치
vector<vector<int>> abilityTable;
for (int i = 0; i < num; i++) {
vector<int> tempVec;
abilityTable.push_back(tempVec);
for (int j = 0; j < num; j++) {
int temp;
cin >> temp;
abilityTable[i].push_back(temp);
}
}
// 팀 0과 1로 구분
vector<int> manList;
for (int i = 0; i < num / 2; i++) {
manList.push_back(0);
}
for (int i = num/2; i < num ; i++) {
manList.push_back(1);
}
vector<int> teamStart;
vector<int> teamLink;
int sumTeamStart;
int sumTeamLink;
int min = 2000000000;
int diff;
do {
sumTeamStart = 0;
sumTeamLink = 0;
teamStart.clear();
teamLink.clear();
// 사람마다의 번호 (0~num-1)을 각 팀 vector에 배분
for (int i = 0; i < manList.size(); i++) {
if (manList[i] == 0) {
teamStart.push_back(i);
}
else {
teamLink.push_back(i);
}
}
// 각 팀의 조합을 점수로 판별
for (int i = 0; i < num/2; i++) {
for (int k = i + 1; k < num / 2; k++) {
sumTeamStart += abilityTable[teamStart[i]][teamStart[k]];
sumTeamStart += abilityTable[teamStart[k]][teamStart[i]];
}
}
for (int i = 0; i < num / 2; i++) {
for (int k = i + 1; k < num / 2; k++) {
sumTeamLink += abilityTable[teamLink[i]][teamLink[k]];
sumTeamLink += abilityTable[teamLink[k]][teamLink[i]];
}
}
diff = abs(sumTeamLink - sumTeamStart);
if (diff < min) {
min = diff;
}
}
while(next_permutation(manList.begin(), manList.end()));
cout << min;
}
<< 깃헙 >>
< 백준 BaekJoon : 1904번 01타일> C++ (0) | 2024.01.27 |
---|---|
< 백준 BaekJoon : 9184번 신나는 함수 실행> C++ (0) | 2024.01.27 |
< 백준 BaekJoon : 14888번 연산자 끼워넣기 > C++ (0) | 2024.01.25 |
< 백준 BaekJoon : 20920번 영단어 암기는 괴로워 > C++ (0) | 2024.01.24 |
< 백준 BaekJoon : 26069번 붙임성 좋은 총총이 > C++ (0) | 2024.01.24 |
댓글 영역