백준 3980번 선발명단

문제링크

문제 해설

접근법

축구는 11명이 해서 다행인 문제다.

왜냐하면 11!이면 약 4천만 이기에 1초 안에 해결이 가능한 문제다.

따라서 브루트포스로 풀이하였다.

풀이

1. 명단을 꾸리기 위해 n번 자리부터 확인한다.
2. player의 능력치가 0이 아니고 이미 선택된 선수가 아닐 경우에 명단에 넣는다.
3. 현재 명단의 총 능력치를 더하고 1번 과정으로 돌아간다.
4. 총 11명이 된다면 능력치의 최대 값을 비교한다.

소스코드

#include <iostream>
#define SIZE 11
using namespace std;

int player[SIZE][SIZE];
int answer;
bool v[SIZE];

void dfs(int cnt, int val) {
	if (cnt == 11) {
		answer = answer > val ? answer : val;
		return;
	}
	for (int i = 0; i < SIZE; i++) {
		if (!v[i] && player[cnt][i] !=0) {
			v[i] = true;
			dfs(cnt + 1, val + player[cnt][i]);
			v[i] = false;
		}
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int tc;
	cin >> tc;
	while (tc--) {
		answer = 0;
		for (int i = 0; i < SIZE; i++) {
			for (int j = 0; j < SIZE; j++) {
				cin >> player[i][j];
			}
		}
		dfs(0, 0);
		cout << answer << "\n";
	}
	

	return 0;
}