[백준 14569번 C/C++] 시간표 짜기

[백준 14569번 C/C++] 시간표 짜기

https://www.acmicpc.net/problem/14569

해결전략

비트마스킹 Bitmasking

정답코드

#include <iostream>
#include <vector>
using namespace std;
 
int n; // 총 과목의 수
int m; // 학생의 수
vector<unsigned long long> lectures;  // 각 과목의 시간표를 비트마스크로 저장할 벡터
 
// 시간표를 비트마스크로 변환하는 함수
unsigned long long ConvertToBitmask(const vector<int>& times)
{
    unsigned long long binary = 0;
 
    for (int i = 0; i < times.size(); i++){
        binary |= (1ULL << times[i]); // 해당 시간에 대응하는 비트를 1로 설정
    }
 
    return binary;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n;
    lectures.resize(n);
    for (int i = 0; i < n; i++)
    {
        int k; // 각 과목의 수업시간의 수
        cin >> k;
        vector<int> times(k);
        for (int j = 0; j < k; j++){
            cin >> times[j];
        }
        lectures[i] = ConvertToBitmask(times); // 수업시간을 비트마스크로 변환하여 저장
    }
 
    cin >> m; // 학생 수
    for (int i = 0; i < m; i++)
    {
        int p; // (각 학생 당) 비어 있는 교시 개수
        cin >> p;
        vector<int> students(p);
        for (int j = 0; j < p; j++){
            cin >> students[j];
        }
 
        unsigned long long studentBitmask = ConvertToBitmask(students);
 
        int cnt = 0; // 학생이 들을 수 있는 과목의 수
        for (int j = 0; j < lectures.size(); j++)
        {
            // 학생의 비어 있는 교시와 과목의 수업시간을 비교하여 학생이 들을 수 있는지 확인
            if ((studentBitmask & lectures[j]) == lectures[j]) {
                cnt++;
            }
        }
 
        cout << cnt << "\n"; // 각 학생이 들을 수 있는 과목의 수 출력
    }
 
    return 0;
}