[BOJ] 3980번 선발 명단

문제 출처: https://www.acmicpc.net/problem/3980

3980번: 선발 명단

 11명의 선수들이 각 포지션별로 능력치가 매겨져 있습니다. 11명의 선수들을 포지션을 잘 정해줘서 능력치의 합이 최대가 되도록 하는게 목표입니다. 11명의 포지션을 재귀를 통해서 정해줍니다. 첫 선수부터 차례대로 해당 포지션의 능력치가 0이 아니고 포지션이 배정이 되어있지 않다면 현재 포지션을 배정해 줍니다. 이런식으로 모든 경우를 계산해서 가장 큰 값을 구해주면 됩니다. 재귀 호출하는 부분에서 방문여부에다가 포지션의 능력치가 0인지를 확인하는 것만 추가해주면 되는 문제였습니다.

 

 

	#include<iostream>
	#include<vector>
	using namespace std;
	int member[11][11];
	bool visited[11];
	vector<int> vt;
	int ans = 0;
	int T;
	void back(int k)
	{
	if (vt.size() >= 11)
	{
	int temp = 0;
	for (int i = 0; i < 11; i++)
	{
	temp += member[i][vt[i]];
	}
	ans = (ans > temp) ? ans : temp;
	return;
	}
	for (int i = 0; i < 11; i++)
	{
	if (!visited[i] && member[k][i])
	{
	visited[i] = true;
	vt.push_back(i);
	back(k + 1);
	vt.pop_back();
	visited[i] = false;
	}
	}
	}
	int main(void)
	{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> T;
	for (int t = 1; t <= T; t++)
	{
	ans = 0;
	for (int i = 0; i < 11; i++)
	{
	for (int j = 0; j < 11; j++)
	{
	cin >> member[i][j];
	}
	}
	back(0);
	cout << ans<<'\n';
	}
	}

view raw 3980.cpp hosted with ❤ by GitHub