[ boj : 11578] 팀원 모집

www.acmicpc.net/problem/11578

11578번: 팀원 모집

문제 : 각 팀원들이 풀 수 있는 문제가 주어지고 모든 문제를 풀 수 있는 팀원들의 조합이 최소의 수가 되는 수를 구해라

 

풀이 : n이 최대가 10 이니 그냥 맘편하게 모든 경우의 수를 돌려보면 됩니다.

재귀함수를 이용해서 depth==m 일때 조건에 맞는지 확인하고 맞으면 최소값을 갱신시켜주는 식으로 풀면 되겠죠

#include<bits/stdc++.h>

using namespace std;

int n, m;
int visit[10],check[11];
int arr[10][11];
int ans = (int)1e9;

void dfs(int depth);
int solve();

int main()
{
	int x;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> x;
		for (int j = 0; j < x; j++)
			cin >> arr[i][j];
	}
	dfs(0);
	cout << (ans != (int)1e9 ? ans : -1);
	return 0;
}
void dfs(int depth)
{
	if (depth == m) {
		ans = min(ans, solve());
		return;
	}

	visit[depth] = 1;
	dfs(depth + 1);

	visit[depth] = 0;
	dfs(depth + 1);
}
int solve()
{
	int ret = 0,cnt=0;
	for (int i = 0; i < m; i++)
		if (visit[i]) {
			for (int j = 0; j <= n; j++) {
				if (arr[i][j] != 0 && !check[arr[i][j]]) {
					check[arr[i][j]] = 1;
					cnt++;
				}
			}
			ret++;
		}
	memset(check, 0, sizeof(check));
	if (cnt == n)return ret;	
	return (int)1e9;
}