[백준OJ] 3980번 선발 명단

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

3980번: 선발 명단

---

 

 

풀이

백트래킹을 이용해서 모든 경우의 수를 구해주며 풀었다.

멤버순서대로 탐색을 해가면서, 0번~10번 포지션까지 순서대로 해당 포지션이 비어있고, 해당선수가 그 포지션의 능력치가 0이 아니라면, 그 자리를 잡은뒤 능력치를 더해주고 다음선수로 넘어간다.

10번선수까지 모두 포지션을 하나씩 잡았다면, 그때 최댓값을 갱신시켜주고 마지막으로 최댓값을 출력해주면 된다.

 

코드

#include<iostream>
#include<algorithm>
using namespace std;

int t;
int member[11][11] = { 0 };
bool check[11] = { 0 };
int ret = 0;

void dfs(int mem,int sum) {
	if (mem == 11) {
		ret = max(ret, sum);
		return;
	}

	for (int i = 0; i < 11; i++) {
		if (!check[i]&&member[mem][i]!=0) {
			check[i] = true;
			dfs(mem + 1,sum+member[mem][i]);
			check[i] = false;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> t;
	while (t--) {
		ret = 0;
		for (int i = 0; i < 11; i++) {
			check[i] = false;
			for (int j = 0; j < 11; j++) {
				cin >> member[i][j];
			}
		}
		dfs(0,0);
		cout << ret << "\n";
	}
	return 0;
}