백준 11378 열혈강호 4 작성일 2021-12-04 | In PS | 문제 링크 https://www.acmicpc.net/problem/11378 알고리즘 이분 매칭 풀이 전체 벌점이 k다. 직원을 기준으로 희망 업무에 매칭시킨 후에, 추가로 매칭이 가능하다면 k만큼 매칭하면 된다. 전체 코드 123456789101112131415161718192021222324252627282930313233343536373839404142import sys input = sys.stdin.readline n, m, k = map(int, input().split()) lst = [[]] for i in range(n): lst.append(list(map(int, input().split()))[1:]) task = [0] * (m+1) def sol(x): if visited[x]: return False visited[x] = 1 for i in lst[x]: if task[i] == 0 or sol(task[i]): task[i] = x return True return False count = 0 for i in range(1, n+1): visited = [0] * (n+1) if sol(i): count += 1 for i in range(1, n+1): while k > 0: visited = [0] * (n+1) if sol(i): k -= 1 count += 1 else: break print(count)