[백준] 14569 시간표 짜기

문제

---

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

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

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

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

 

 

 

 

풀이

---

비트 마스크를 이용하여 풀이를 하였다.

 

예제를 보면서 풀이를하면

3

4 1 2 3 4

6 5 6 7 8 9 10

4 11 21 31 41

5

8 1 2 3 4 5 6 7 8

7 1 2 3 7 8 9 10

14 1 2 3 4 5 6 7 8 9 10 11 21 31 41

5 41 42 43 44 45

10 1 5 6 7 8 9 10 11 21 31

 

에서 첫번째 학생을 비트마스크를 이용해서 표현을 하면

11110(2) 가 된다.

 

첫번째 수업을 비트마스크를 이용해서 표현을 하면

111111110(2) 가 된다.

 

이 두개가 서로 맞는지를 판단하기 위해 첫번째 수업의 값을 ~(NOT) 연산을 이용해 바꿔준다.

 

00000001(2) 이 될것이다.

이렇게 두개의 값을 &(AND) 연산을 통해서 0인지를 판단하면 된다.

 

1번학생	0	0	0	0	1	1	1	1	0
~1번 수업	0	0	0	0	0	0	0	0	1
값	0	0	0	0	0	0	0	0	0

이 되어 둘은 맞는 수업이라고 할 수 있다.

서로 불가능한 수업에서는 0 보다 큰값이 나오게 된다.

 

<전체코드>

import java.io.*;
import java.util.*;
import java.util.regex.*;

public class Main {	

	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		long[] timetable = new long[1001];
		
		int n = Integer.parseInt(bufferedReader.readLine());
		for(int i = 0 ; i < n ; i++) {
			StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
			
			int k = Integer.parseInt(st.nextToken());
			for(int j = 0 ; j < k ; j++) {
				int time = Integer.parseInt(st.nextToken());
				timetable[i] |= ((long)1 << time);
			}
			
		}
		
		int m = Integer.parseInt(bufferedReader.readLine());
		for(int i = 0 ; i < m ; i++) {
			StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
			
			int size = Integer.parseInt(st.nextToken());
			long tmp = 0;
			for(int j = 0 ; j < size ; j++) {
				int time = Integer.parseInt(st.nextToken());
				tmp |= ((long)1 << time);
			}
			
			tmp = ~tmp;
			
			int cnt = 0; for(int j = 0 ; j < n ; j++) { 
				if((tmp & timetable[j]) == 0) {
					cnt++; 
				} 
			}
			 sb.append(cnt +"\n");
		}
		
		System.out.println(sb);
	}
	
}