[백준] 14569 - 시간표 짜기

문제 링크

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

문제 요약

주어진 문제는 여러 개의 강의 시간표와 학생의 개인 일정이 주어졌을 때, 각 학생이 들을 수 있는 강의의 수를 구하는 문제입니다.

• 강의마다 특정 시간대에 수업이 열리며, 이 시간대는 1부터 50까지의 번호로 표현됩니다.
• 학생은 자신의 일정과 강의 시간표가 겹치지 않는 강의만 수강할 수 있습니다.
• 학생의 시간표와 강의 시간표가 겹치지 않으려면, 학생의 일정에 포함된 시간이 강의 시간표에 완전히 포함되어야 합니다.

푼 방법

이 문제는 비트마스크를 활용하여 각 강의의 시간표와 학생의 일정을 이진수로 표현하고, 비트 연산을 통해 겹치는 시간이 있는지 확인하는 방식으로 해결할 수 있습니다.

1. 비트마스크로 강의 시간표 표현

• 각 강의는 여러 시간대에 열리므로, 각 시간대를 비트로 표현합니다. 이를 위해 temp_num이라는 변수를 사용하여 각 강의 시간에 대해 해당 비트를 켭니다.
  • 예를 들어, 3, 5, 7번째 시간에 수업이 열린다면, temp_num은 1010100과 같은 이진수로 표현됩니다.
• 이렇게 각 강의의 시간표를 비트마스크로 변환하여 리스트 course에 저장합니다.

2. 학생의 일정도 비트마스크로 변환

• 학생의 일정 역시 비트마스크로 변환합니다. 학생이 일정이 없는 시간대에 해당하는 비트를 켜서 schedule에 저장합니다.

3. 비트 연산을 통한 비교

• 각 강의와 학생의 일정을 비교하기 위해, 비트 AND 연산을 사용합니다.
  • course[j] & schedule == course[j]: 이 조건은 강의 시간표 course[j]가 학생의 빈 일정 schedule에 완전히 포함되는지 확인하는 조건입니다. 즉, 강의 시간이 학생의 빈 일정에 모두 포함되는 경우, 해당 강의를 수강할 수 있음을 나타냅니다.

4. 결과 계산

• 모든 강의에 대해 학생의 시간표와 비교한 후, 수강할 수 있는 강의의 개수를 세어 출력합니다.

정답 코드

import sys
n = int(sys.stdin.readline().rstrip())
course = []
for _ in range(n):
    temp = list(map(int, sys.stdin.readline().split()))
    temp_num=0
    for j in range(1, temp[0]+1):
        temp_num |= (1 << temp[j])
    course.append(temp_num)
    
m = int(sys.stdin.readline().rstrip())
for _ in range(m):
    temp = list(map(int, sys.stdin.readline().split()))
    schedule = 0
    for j in range(1, temp[0]+1):
         schedule |= (1 << temp[j])
    result = 0
    for j in range(n):
        if course[j] & schedule == course[j]:
            result+=1
    print(result)