[백준 11578] 팀원 모집 (C++)

문제 링크: https://www.acmicpc.net/problem/11578

11578번: 팀원 모집

1. 주의할 점

- 팀원을 생성할 수 없는 경우 -1을 출력한다

- 2^N -1(N이 최대 10)만큼 만들 수 있는 팀원 경우의수를 모두 구할수 있어야 한다(2^N 이상으로 구하면 어떤 경우에서 시간초과가 발생할 수 있다)

 

2. 구현

- 팀원 1명, 2명, 3명,....N명일 때 만들 수 있는 조합의 수를 따진다.

  전부 구해도 nC1 + nC2 + nC3 +... +nCn = 2^n -1 이므로 시간초과가 발생하지 않는다.

- 팀원을 구한 후, 해당 팀원으로 모든 문제를 풀 수 있다면 result값을 변경한다.

- Result값보다 크거나 같은 수의 사람이 필요로 하는 경우는 볼 필요가 없다(이미 가장 적은 인원의 팀이 아니므로) ->    시간단축 가능

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> can_solve[11];		//index번 학생이 풀 수 있는 문제
vector<int> team;
int problem, people, val, num, result = 11;

void dfs(int cnt, int idx) {		//포함한 사람 수, 이후 사람
	if (cnt >= result) return;		//현재 저장된 값보다 많은 수의 사람이 필요한 경우 return
	if (cnt > 0) {
		bool solved[11] = { false, };		
		for (int i = 0; i < cnt; i++) {
			int cidx = team[i];
			//현재 팀으로 풀 수 있는 문제 검사
			for (int j = 0; j < can_solve[cidx].size(); j++)
				solved[can_solve[cidx][j]] = true;
		}
		bool avail = true;
		for (int i = 1; i <= problem; i++) {
			if (!solved[i]) {
				avail = false;
				break;
			}
		}
		//모든 문제를 풀 수 있다면 최소 팀원 갱신
		if (avail)
			result = min(result, cnt);		
	}
	if (idx > people) return;
	for (int i = idx; i <= people; i++) {
		team.push_back(i);
		dfs(cnt + 1, i + 1);
		team.pop_back();
	}
}

int main() {
	cin >> problem >> people;
	for (int i = 1; i <= people; i++) {
		cin >> val;
		for (int j = 0; j < val; j++) {
			cin >> num;
			can_solve[i].push_back(num);
		}
	}
	dfs(0, 1);
	if (result == 11) result = -1;
	cout << result;
	system("pause");
	return 0;
}