백준 11578 팀원 모집

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

11578번: 팀원 모집

 

문제

2015년 11월 28일은 기다리고 기다리던 제1회 IUPC가 열리는 날이다. IUPC는 Inha University Programming Contest의 약자로 인하대학교 IT공대 학부생이면 누구나 참여할 수 있는 프로그래밍 경시대회이다. IUPC의 총상금은 무려 110억 원이나 되며 고급스러운 점심과 많은 다과가 제공되어 참가자들이 대회에 집중할 수 있도록 최적의 환경을 제공한다. 그중 참가자들을 진정 열광시키는 것은 수많은 팀에게 추첨을 통해 문화상품권을 나눠준다는 점이다. 컴퓨터정보공학과에 재학 중인 강호는 대회에 참가하기 위해 팀원을 모집하려고 한다. IUPC가 여타 많은 대회와 다른 점이 있다면 문제의 수가 많고 팀원의 수가 무제한이라는 것이다. IUPC에서 모든 문제를 다 풀어 우승한 뒤 엄청난 부와 명예를 챙기고 싶은 강호는 모든 문제를 풀 수 있는 팀을 만들고 싶어 한다. 하지만 팀원의 수가 많으면 많을수록 자신에게 돌아오는 상금이 적어지기 때문에 최소한의 팀원으로 대회를 우승하고 싶어 한다. 강호가 선택할 수 있는 팀원의 목록과 각각의 팀원들이 해결할 수 있는 문제의 번호들이 주어졌을 때 강호가 IUPC에서 최소한의 팀원으로 모든 문제를 다 풀어 우승할 수 있도록 팀을 만들어보자.

 

 

해결 방법 

비트마스킹 브루트포스(조합)

 

비트마스킹을 모르면 구현이 불편하다. 비트마스킹 

 

대략적인 코드 설명

학생 수 가장 적은 조합부터 확인하면서 모든 문제를 풀 수 있는지 확인, 풀 수 있다면 그 때의 학생수 return

모두 확인 했음에도 풀 수 없으면 -1 return

 

import sys
input = sys.stdin.readline
from itertools import combinations

n, m = map(int, input().split())

s = [0] * m
answer = 0
flag = 0 

for i in range(n):
    answer |= (1 << i)

for i in range(m):
    tmp = (list(map(int, input().split())))
    for j in tmp[1:]:
        s[i] |= (1 << j-1)

def find():
    for i in range(1,m+1):
        d = list(combinations(s,i))
        for probs in d:
            tmp = 0
            for prob in probs:
                tmp |= (prob)
                if answer == tmp:
                    return i
    return -1 
                
print(find())