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

문제링크 : https://www.acmicpc.net/problem/14569

14569번: 시간표 짜기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M, K, P, ti, qi;
vector<bitset<51>> t;
vector<bitset<51>> q;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;
    t.resize(N);
    for(int i=0; i<N; i++)
    {
        cin >> K;
        for(int j=0; j<K; j++)
        {
            cin >> ti;
            t[i].set(ti);
        }
    }

    cin >> M;
    q.resize(M);
    for(int i=0; i<M; i++)
    {
        cin >> P;
        for(int j=0; j<P; j++)
        {
            cin >> qi;
            q[i].set(qi);
        }

        int cnt = 0;
        for(int j=0; j<N; j++)
        {
            if(t[j] == (t[j] & q[i])) cnt++; //가능한 과목 카운트
        }
         cout << cnt << "\n";
    }

    return 0;
}

비트마스킹 문제이다.

이번에 처음으로 bitset을 간단하게나마 써보았다.

 

처음에 각 과목의 교시에 대해 set을 통해서 비트값으로 저장해준다.

이후 비어 있는 교시에 대해서도 마찬가지로 set을 통해서 비트값으로 저장해준다.

 

만약 현재 교시에 대해  비어있는 교시의 케이스가 존재한다면 이를 카운팅해주면 된다.

여기서 비트로 계산하므로 현재 교시(t[j]) 과 비어있는 교시(q[i])를 곱해준다.

만약 곱해주면 없는 값에 대해서는 0으로 없어지므로 앞에 값이 같다면 같아지게 된다.

결과적으로 서로 값이 같은지를 체크해주게 되는 것이다.

ex) 교시 : 1, 2, 3, 4 / 비어있는 교시 1, 2, 3, 4, 5 -> 곱할시 5는 없어지므로 맞는 케이스가 된다.