백준 2128 마지막 조별 시합 / python

문제 : 2128

풀이 point

문제 개수가 15개이기 때문에 미리 K개의 문제를 뽑아 놓고 문제를 풀 수 있는 학생을 구한다.

우선, K개 만큼의 문제를 뽑아 모든 조합을 만든다.
학생A가 풀 수 있는 문제가 뽑힌 K개 문제의 부분집합인지 확인한다.
이를 학생 수 N번 만큼 반복하여 가장 최대 학생 수를 구한다.

풀이 방법

조합을 직접 구현하여 구할 수도 있고, python 모듈
from itertools import combinations를 통해서도 구할 수 있다. 나는 공부를 위해서 직접 구현하였다.

#백준 2128, 마지막 조별 시합

import sys
input = sys.stdin.readline

N, D, K = map(int, input().rstrip().split())

inform = []
pickedProblems = []
answer = 0

for i in range(N):
    data = list(map(int, input().rstrip().split()))
    problems = data[1:]
    inform.append(set(problems))

def countStudents(setPicked):
    cnt = 0
    for s in inform:
        if s.issubset(setPicked): #부분집합인지 확인
            cnt += 1
    return cnt

def pickProblem(depth, start):
    global answer

    if depth == K:
        setPicked = set(pickedProblems) #issubset비교를 위해 set 형변환
        answer = max(answer, countStudents(setPicked))
        return

    if D - start + 1 < K - depth: 
        return

    for i in range(start, D+1):
        pickedProblems.append(i)
        pickProblem(depth+1, i+1)
        pickedProblems.pop()

pickProblem(0, 1)
print(answer)