[백준] 3980 선발명단
✔️ 문제 링크
https://www.acmicpc.net/problem/3980
3980번: 선발 명단
문제 챔피언스 리그 결승전을 앞두고 있는 맨체스터 유나이티드의 명장 퍼거슨 감독은 이번 경기에 4-4-2 다이아몬드 전술을 사용하려고 한다. 오늘 결승전에 뛸 선발 선수 11명은 미리 골라두었지만, 어떤 선수를 어느 포지션에 배치해야 할지 아직 결정하지 못했다. 수석코치 마이크 펠란은 11명의 선수가 각각의 포지션에서의 능력을 0부터 100가지의 정수로 수치화 했다. 0은 그 선수가 그 포지션에 적합하지 않다는 뜻이다. 이때, 모든 선수의 포지션을 정하는
www.acmicpc.net
✔️ 문제 이해
1. 11명의 축구팀을 구성해야한다.
2. 11명의 선수의 각각의 포지션에 대한 능력치가 0부터 100까지 주어진다. (포지션은 11개)
3. 능력치의 합이 최대가 되는 모든 선수의 포지션을 정하고, 능력치 합을 출력해야한다.
4. 각 선수는 능력치가 0인 포지션에 배치될 수 없다.
✔️ 설계
1. 11개의 포지션에 11명의 선수를 배치하는 모든 경우를 구해본다.
2. 즉, 11개중에 11개를 뽑는 순열이다. 11P11 는 39,916,800 약 4천만이다.
3. 즉, 모든 선수에게 포지션을 배치하는 4천만 가지의 경우의수가 있고, 각 경우의 수마다 능력치 합을 계산하는 작업을
수행해야 하므로, 시간복잡도에 유의해야한다. (참고로 제한 시간은 1초이다.)
4. 순열을 만들때, 포지션이 0인 경우는 제외하도록 해서 시간복잡도를 줄인다.
✔️ 문제 회고
1. 순열이 떠올라서 빨리 풀었다. 하지만 시간초과가 발생했다.
2. 포지션이 0인 경우는 순열을 만들지 않도록 처리해서 시간을 줄였다.
3. 비트마스크로 더 간단히 문제를 풀 수 있을 것 같다. 나중에 풀어보자.
👨🏻💻 소스 코드
#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
int n;
int capability[11][11];
int res = -0x7fffffff;
bool visited[11];
vector<int> v;
void permutation() {
if (v.size() == 11) {
int sum = 0;
for (int i = 0; i < 11; i++) {
sum += capability[i][v[i]]; //i번 선수에 v[i] 포지션을 줬을 때의 능력치 계산
}
res = max(res, sum);
return;
}
for (int i = 0; i < 11; i++) {
if (!visited[i] && capability[v.size()][i] != 0) {//포지션이 0이라면, 순열을 만들지 않는다.
visited[i] = true;
v.push_back(i);
permutation();
v.pop_back();
visited[i] = false;
}
}
}
int main() {
cin >> n;
while (n--) {//테스트 케이스 n개
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
cin >> capability[i][j]; //선수들의 능력치를 입력받는다.
}
}
permutation();
cout << res << endl;
res = -0x7fffffff;
}
return 0;
}