어흥
[백준 11578] 팀원 모집 (C++) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/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;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 6118] 숨바꼭질 (C++) (0) | 2020.03.12 |
---|---|
[백준 16179] 두 동전 (C++) (0) | 2020.03.11 |
[백준 1068] 트리 (C++) (0) | 2020.03.11 |
[백준 15989] 1,2,3 더하기 4 (C++) (0) | 2020.03.11 |
[백준 1072] 게임 (C++) (0) | 2020.03.11 |
Comments