[백준] 3980 선발명단

✔️ 문제 링크

https://www.acmicpc.net/problem/3980

3980번: 선발 명단

---

✔️ 문제 이해

 

11가지 포지션

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;
}