반응형
https://www.acmicpc.net/problem/11578
11578번: 팀원 모집
3번 학생과 4번 학생을 선택하면 1번부터 5번까지 모든 문제를 풀 수 있는 팀을 만들 수 있다. 1번, 2번, 4번 학생을 선택해도 모든 문제를 다 풀 수 있지만 팀원의 수가 3명이라 답이 될 수 없다.
www.acmicpc.net

[ 문제풀이 ]
1. 1부터 2M - 1까지 for문을 이용해 돌면서 해당 비트가 1이라면 해당 팀원이 풀 수 있는 문제들을 풀고, cnt++를 해준 후 모든 문제를 풀었다면 가장 낮은 cnt를 ans에 저장해 줍니다.
2. ans가 갱신되지 않았다면 -1을 출력하고 그렇지 않다면 ans를 출력합니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | #include<iostream> #include<vector> #include<cmath> using namespace std; int N, M; vector<int> list[11]; int ans = 987654321; int mask; void check(int num) { int tmp = 0; int cnt = 0; for (int i = 0; i < M; i++) { if (num & 1 << i) { for (auto& next : list[i]) { tmp |= 1 << next; } cnt++; } } if (tmp == mask) { ans = min(ans, cnt); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> M; for (int i = 0; i < M; i++) { int n; cin >> n; for (int j = 0; j < n; j++) { int tmp; cin >> tmp; list[i].push_back(tmp); } } mask = pow(2, N + 1) - 2; for (int i = 1; i < pow(2, M); i++) { check(i); } if (ans == 987654321) cout << -1; else cout << ans; } | cs |
반응형
'백준' 카테고리의 다른 글
[ 백준 ] 17433번 - 신비로운 수 (C++) (0) | 2023.10.21 |
---|---|
[ 백준 ] 1684번 - 같은 나머지 (C++) (0) | 2023.10.20 |
[ 백준 ] 19591번 - 독특한 계산기 (C++) (0) | 2023.10.18 |
[ 백준 ] 14699번 - 관악산 등산 (C++) (1) | 2023.10.17 |
[ 백준 ] 13544번 - 수열과 쿼리 3 (C++) (0) | 2023.10.16 |