[Python/파이썬] 백준 11578번: 팀원 모집

문제

 

풀이

비트 마스킹을 사용하여 입력

n, m = map(int, input().split())
arr = [0b0000000000] * (m + 1)

for i in range(1, m + 1):
    question = list(map(int, input().split()))[1:]
    for q in question:
        arr[i] |= (1 << q)

 

브루트 포스를 위해 m + 1번 반복

for ans in range(1, m + 1):
    tmp = set()
    for i in range(len(arr)):
        if arr[i] == 2 ** (n + 1) - 2:
            print(ans)
            exit()
        for j in range(i + 1, len(arr)):
            tmp.add(arr[i] | arr[j])
    arr = list(tmp)

 

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [0b0000000000] * (m + 1)

for i in range(1, m + 1):
    question = list(map(int, input().split()))[1:]
    for q in question:
        arr[i] |= (1 << q)

for ans in range(1, m + 1):
    tmp = set()
    for i in range(len(arr)):
        if arr[i] == 2 ** (n + 1) - 2:
            print(ans)
            exit()
        for j in range(i + 1, len(arr)):
            tmp.add(arr[i] | arr[j])
    arr = list(tmp)

print(-1)

 

마무리

비트 마스킹을 공부하기 위해 풀은 문제