[백준] 14569 시간표 짜기

문제 링크

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

문제 요약

1. 친구들의 비어 있는 시간표에 과목을 추가할 수 있는 경우의 수를 세는 문제입니다.
2. 월요일 1~4교시를 차지하는 과목과 월요일 2~5교시를 차지하는 과목은 모두 후보가 될 수 있습니다.
3. 겹치는 시간이 있어도 상관없이 비어 있는 시간에 들어갈 수 있는 모든 과목을 후보로 포함합니다.

푼 방법

이 문제는 시간표를 효율적으로 관리하고 비어 있는 시간과 과목 시간을 빠르게 비교하기 위해 비트마스킹을 사용할 수 있습니다.

1. 비트마스킹을 사용하여 각 교시를 비트로 표현합니다. 예를 들어, 월요일 1~5교시가 비어 있다면 비어 있는 시간을 5비트로 표현할 수 있습니다.
2. 과목의 시간표도 같은 방식으로 비트로 표현하고, 비어 있는 시간과 AND 연산을 사용하여 겹치는 시간을 빠르게 확인합니다.
3. AND 연산 결과가 과목 시간표와 같다면 해당 과목은 후보가 될 수 있습니다.

정답 코드

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)

배웠던 부분

비트마스킹 알고리즘 이해하기

• 비트마스킹은 이진수 비트를 활용하여 데이터 집합을 압축적으로 표현하는 기법입니다.
• 각 비트는 하나의 상태나 정보를 나타내므로, 시간표와 같이 교시마다 상태가 필요한 경우에 유용하게 사용할 수 있습니다.
• AND 연산을 사용하여 특정 상태를 확인하거나, OR 연산을 통해 상태를 추가하거나 변경할 수 있습니다.