[C++] 백준 3980번: 선발 명단

문제 링크

3980번: 선발 명단

문제 요약

11명의 선수들이 있고, 11개의 포지션이 있다. 각 선수들이 어떤 포지션에서 뛰는지에 따라서 능력치가 달라진다. 각 선수와 포지션에 대한 능력치가 모두 주어진다. 만약 선수가 특정 포지션에서 뛸 수 없다면 능력치가 0으로 주어진다. 선수별로 뛸 수 있는 포지션은 최대 5개이다. 이때 팀 능력치의 최댓값을 구해야 한다.

접근 방법

쉬운 브루트포스 문제이지만 문제를 잘못 읽어서 TLE를 한 번 받고, 실수를 해서 WA를 한 번 받았습니다.

11개의 선수들에 대해서 방문 가능한 경우에만 매칭을 모두 시켜주고 최댓값을 매번 갱신해주면 됩니다. 간단한 백트래킹으로 구현이 가능한 쉬운 문제입니다.

다만, 처음에는 능력치가 0일때는 아예 해당 포지션에서 뛸 수 없다는 사실을 간과해서 TLE를 받았었고, 그 다음에는 매 TC마다 결과를 저장하는 변수를 초기화해야하는 것을 깜빡해서 WA를 받았습니다. 문제를 잘 읽어야 한다는 교훈을 주기적으로 얻고 있습니다...

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 12;
int status[MAX][MAX], ans = 0;
bool visited[MAX];

void func(int cnt, int sum)
{
	if (cnt == MAX)
		ans = max(ans, sum);
	
	for (int i = 1; i < MAX; i++)
	{
		if (!visited[i] && status[cnt][i])
		{
			visited[i] = true;
			sum += status[cnt][i];
			func(cnt + 1, sum);
			sum -= status[cnt][i];
			visited[i] = false;
		}
	}
}

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

	int t;
	cin >> t;

	while (t--)
	{
		for (int i = 1; i <= 11; i++)
			for (int j = 1; j <= 11; j++)
				cin >> status[i][j];

		func(1, 0);
		cout << ans << '\n';
		ans = 0;
	}

	return 0;
}