백준 11578 팀원 모집

오늘도 비트마스킹 문제이다. 너무 시간이 늦어 쉬운거를 잡았다. 스스스슥 풀어서 다행이다. 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;
}

 

가벼운 문제라도 왠지 계속 풀고 싶어서 잡았다. 조금 더 어려운 것도 슬슬 풀어봐야겠다.

우리인생 화이팅.

 

오늘도 평온한 하루가 되길. 슨민.