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

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

문제

---

연세대학교 수강신청 기간이 시작되었다. 많은 친구들은 비어 있는 시간에 어떤 과목을 추가로 신청할 수 있는지를 궁금해 한다.

이 친구들이 비어 있는 시간에 추가로 신청할 수 있는 과목의 후보 개수를 구해보자.

후보 개수를 세는 것이므로 현재 내 시간표에서 신청할 수 있는 과목끼리 시간이 겹치더라도 모두 세어야 한다.

즉, 월요일 1, 2, 3, 4, 5교시 시간이 비어 있고 한 과목의 시간이 월요일 1, 2, 3, 4교시이고 나머지 한 과목의 시간이 월요일 2, 3, 4, 5교시라면 2과목 모두 후보가 될 수 있다.

 

입력

---

연세대학교의 총 과목의 수 N (3 ≤ N ≤ 1000)이 주어진다.

N줄에 걸쳐서 각 과목의 수업시간의 수 k (4 ≤ k ≤ 50)가 주어지고 그 옆에 k개의 숫자 ti (1 ≤ ti ≤ 50)가 공백으로 구분되어 주어진다.

ti는 이 과목의 수업이 진행되는 교시를 의미하며 1 ~ 50의 값을 가진다.

(월요일 1~10교시: 1~10, 화요일 1~10교시: 11~20, …)

다음 줄에 학생수 M (1 ≤ M ≤ 10000) 이 주어진다.

M줄에 걸쳐서 각 학생들의 비어 있는 교시 개수 p (0 ≤ p ≤ 50)가 주어지고 그 옆에 p개의 숫자 qi (1 ≤ qi ≤ 50)가 공백으로 구분되어 주어진다.

Ex) 알고리즘의 수업시간이 화요일 2, 3교시, 수요일 4, 5교시라면 다음과 같이 입력이 주어진다.

4 12 13 24 25

 

출력

---

M줄에 걸쳐서 각 학생들의 들을 수 있는 과목 개수를 출력한다.

 

문제 풀이

---

비트마스킹 문제.

 

수업 시간과 비어 있는 교시를 비트화하여 저장한다. 0~49 자리까지의 비트를 이용하여 수업 시간과 학생들의 비어 있는 과목을 long long 타입으로 저장해준다. 수업 시간과 학생의 비어 있는 교시를 해당 교시를 포함시키는 연산은 set에 추가하는 연산, 즉 or 연산을 이용해주면 된다.

학생의 비어 있는 시간 안에 한 과목의 모든 수업 시간이 포함되어야 하므로 두 숫자를 and 연산해준다. 모든 수업 시간이 가능할 때에만 and 연산했을 때 과목의 수업 시간에 해당하는 값이 나온다.

 

아래는 코드.

#include <iostream>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, K, T, M, P, Q;
	int answer = 0;
	cin >> N;
	long long* arr = new long long[N];
	for (int i = 0; i < N; i++)
	{
		cin >> K;
		arr[i] = 0;
		for (int j = 0; j < K; j++)
		{
			cin >> T;
			arr[i] |= (1LL << (T-1));
		}
	}
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		long long m = 0;
		answer = 0;
		cin >> P;
		for (int j = 0; j < P; j++)
		{
			cin >> Q;
			m |= (1LL << (Q-1));
		}
		for (int j = 0; j < N; j++)
		{
			if ((m & arr[j]) == arr[j])
			{
				answer++;
			}
		}
		cout << answer << "\n";
	}
	return 0;
}