오늘도 비트마스킹 문제이다. 너무 시간이 늦어 쉬운거를 잡았다. 스스스슥 풀어서 다행이다. 2트만에 패스띄웠다...
학생과 알고리즘 모두 10개까지밖에 안들어온다. 그냥 전체를 순회하면서 돌아도 오래 걸리지 않을 듯 하다.
학생을 입력 받을때, 학생이 풀 수 있는 알고리즘들을 비트마스킹된 값의 배열로 저장을 한다.
이후, 학생이 뽑힐 수 있는 경우의 수(학생이 m번까지 있으므로, 2^m 가지의 수)를 순회하면서, 포함된 학생들이 풀 수 있는것들을 전부 or처리한다. 그 상태가 모든 문제를 풀 수 있는 상태(5 문제이면 ~00011111) 인지 확인하고, 이때마다 최소값을 구해주면 된다.
N과 M이 더 많이 커지면 이 방법으로는 되지 않을 것 같다. 경우의 수가 크지 않아 전체 탐색으로도 오래 걸리지 않았다...
#include <iostream>
int main()
{
int n, m;
std::cin >> n >> m;
int std[m];
for (int i = 0; i < m; i++)
{
int cnt;
std::cin >> cnt;
std[i] = 0;
for (int j = 0; j < cnt; j++)
{
int algo;
std::cin >> algo;
std[i] = std[i] | (1 << (algo - 1));
}
}
int team = m + 1;
for (int i = 1; i < (1 << m); i++)
{
int stat = 0;
int memb_cnt = 0;
for (int j = 0; j < m; j++)
{
if (i & (1 << j))
{
memb_cnt++;
stat = stat | std[j];
}
}
if (stat == (1 << n) - 1)
team = std::min(team, memb_cnt);
}
if (team != m+1)
std::cout << team;
else
std::cout << -1;
}
가벼운 문제라도 왠지 계속 풀고 싶어서 잡았다. 조금 더 어려운 것도 슬슬 풀어봐야겠다.
우리인생 화이팅.
오늘도 평온한 하루가 되길. 슨민.
'짜잘한 기록' 카테고리의 다른 글
백준 9328 열쇠 (0) | 2021.10.22 |
---|---|
백준 1562 계단 수 (0) | 2021.10.21 |
백준 13701 중복 제거 (0) | 2021.10.19 |
백준 6568 귀도 반 로썸은 크리스마스날 심심하다고 파이썬을 만들었다 (1) | 2021.10.18 |
백준 1126 같은 탑 (0) | 2021.10.16 |