728x90
https://www.acmicpc.net/problem/3980
3980번: 선발 명단
문제 챔피언스 리그 결승전을 앞두고 있는 맨체스터 유나이티드의 명장 퍼거슨 감독은 이번 경기에 4-4-2 다이아몬드 전술을 사용하려고 한다. 오늘 결승전에 뛸 선발 선수 11명은 미리 골라두었지만, 어떤 선수를 어느 포지션에 배치해야 할지 아직 결정하지 못했다. 수석코치 마이크 펠란은 11명의 선수가 각각의 포지션에서의 능력을 0부터 100가지의 정수로 수치화 했다. 0은 그 선수가 그 포지션에 적합하지 않다는 뜻이다. 이때, 모든 선수의 포지션을 정하는
www.acmicpc.net
#include <iostream>
#include <vector>
using namespace std;
int ability[11][11];
vector<int> result(11);
int maxTotal = 0;
void select(vector<bool> visited, int num) {
if (num == 11) {
int total = 0;
for (int i = 0; i < 11; i++) {
total += ability[i][result[i]];
}
if (total > maxTotal) maxTotal = total;
return;
}
for (int i = 0; i < 11; i++) {
if (ability[num][i] != 0 && !visited[i]) {
visited[i] = true;
result[num] = i;
select(visited, num + 1);
visited[i] = false;
}
}
}
int main() {
cin.tie(NULL);
vector<bool> person(11);
vector<bool> position(11);
int testCase;
cin >> testCase;
for (int t = 0; t < testCase; t++) {
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
cin >> ability[i][j];
}
}
vector<bool> visited(11);
maxTotal = 0;
select(visited, 0);
cout << maxTotal << '\n';
}
return 0;
}
728x90
'알고리즘 문제' 카테고리의 다른 글
[백준] 5585번 거스름돈 (0) | 2020.02.21 |
---|---|
[백준] 10995번 별 찍기 - 20 (0) | 2020.02.20 |
[백준] 1182번 부분수열의 합 (0) | 2020.02.20 |
[백준] 4948번 베르트랑 공준 (0) | 2020.02.20 |
[백준] 3671번 산업 스파이의 편지 (0) | 2020.02.20 |