[백준] 3980 선발 명단 c++

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

3980번: 선발 명단

 

브루트포스 알고리즘이 떠올랐는데 시간초과가 날까 걱정했다.

계산 횟수가 많을 것 같아서 고민해서 태그를 봤는데 브루트 포스 알고리즘이였다.

계산량 계산하는 것이 아직 어려웠다.

풀이

백트래킹을 통해서 선수들이 포지션을 가질 수 있는 모든 경우의 수를 계산한다.

주의 해야될 점은 아래 사진처럼 (0,0) , (1,1) , (2 , 2) 를 선택하고 3번째 선수로 넘어갈때

2번째 포지션은 이미 2번 째 선수가 가져가서  3번째 선수는 포지션을 가질 수 없다.

이런 상황일때 아래 코드 34 번째 줄 처럼 return을 해주어서 그 전 선수들의 포지션을 다시 정해주어야한다.

 

출처 https://www.acmicpc.net/board/view/36219

 

#include<iostream>
#include<cstring>

using namespace std;



int t;
int ability[11][11];
int ans;
int num = 11;
bool check[11];
void selection(int n,int sum)
{
	if (n == num)
	{
		if (sum > ans)
			ans = sum;
		return;
	}
	for (int i = n; i < num; i++)
	{
		for (int j = 0; j < num; j++)
		{
			if (ability[i][j] != 0 && !check[j])
			{
				check[j] = true;
				sum += ability[i][j];	
				selection(i + 1, sum);
				sum -= ability[i][j];;
				check[j] = false;
			}
		}
		return;//포지션을 하나도 가지지 못했을 때 return
		
	}
	
	
}
int main()
{
	cin >> t;
	while (t--)
	{
		for (int i = 0; i < num; i++)
			for (int j = 0; j < num; j++)
			{
				cin >> ability[i][j];
			}
		selection(0,0);
		cout << ans << endl;
		memset(ability, 0, sizeof(ability));
		memset(check, 0, sizeof(check));

		ans = 0;

	}
}