알고리즘
백준 3980번 선발 명단 C++
영춘권의달인
2023. 1. 3. 12:35
https://www.acmicpc.net/problem/3980
3980번: 선발 명단
각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다.
www.acmicpc.net
백트래킹, 능력치가 0이면 배치할 수 없다는 것이 핵심
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>
using namespace std;
using int64 = long long;
vector<vector<int>> abilities;
vector<bool> included;
int ans;
void BT(int pos, int sum) {
if (pos >= 11) {
ans = max(ans, sum);
return;
}
for (int i = 0; i < 11; i++) {
if (included[i]) continue;
int ability = abilities[i][pos];
if (ability == 0) continue;
included[i] = true;
sum += ability;
BT(pos + 1, sum);
included[i] = false;
sum -= ability;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
abilities = vector<vector<int>>(11, vector<int>(11));
int t;
cin >> t;
while (t--) {
ans = -1;
included = vector<bool>(11, false);
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
cin >> abilities[i][j];
}
}
BT(0, 0);
cout << ans << "\n";
}
}