[파이썬/python] 백준 11578 - 팀원 모집

문제

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

---

문제 설명

1. 모든 문제를 풀 수 있는 팀을 만들어야 한다.
2. 팀원의 수가 많을수록 상금이 적어지기 때문에 최소한의 팀원으로 우승해야 한다.

---

풀이

각각의 팀원들을 묶어가며 해당 팀원들로 모든 문제를 풀 수 있는지 확인하는 문제이다.
브루트포스를 통해 하나씩 비교해가며 풀 수 있다. 하지만 각각의 문제를 하나의 비트라고 생각하고 모든 비트가 채워졌을 때 우승할 수 있다고 생각하여 비트마스킹을 이용했다.

 

1. 각 학생이 풀 수 있는 문제를 비트 처리하여 students 배열에 넣는다.
2. students 배열의 학생들을 조합을 이용하여 해당 조합이 우승이 가능한 지 확인한다.
3. 인원이 적은 순으로 확인하기 때문에 가장 먼저나온 조합이 최소한의 팀원이므로 팀원 수를 반환한다.

---

코드

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

N,M = map(int,input().split())
students = []
is_win = 0
for i in range(N):
    is_win |= (1 << i)
res = -1


for _ in range(M):
    student = 0
    for p in list(map(int,input().split()))[1:]:
        student |= (1 << p-1)
    students.append(student)

def cal():
    for i in range(1, M+1):
        for cur_student in combinations(students,i):
            tmp_st = 0
            for st in cur_student: 
                tmp_st |= st
            if tmp_st == is_win:
                return i
    return -1

print(cal())

---

시간복잡도

• 조합의 경우의 수를 모두 구한다. -> $O(2^m)$
• 학생 조합을 비트 처리 한다. -> $O(1)$
• m이 10일 때 최악, 약 $O(1024)$의 시간이 걸린다.