시간 제한 | 메모리 제한 |
2초 | 256MB |
문제
2015년 11월 28일은 기다리고 기다리던 제1회 IUPC가 열리는 날이다. IUPC는 Inha University Programming Contest의 약자로 인하대학교 IT공대 학부생이면 누구나 참여할 수 있는 프로그래밍 경시대회이다.
IUPC의 총상금은 무려 110억 원이나 되며 고급스러운 점심과 많은 다과가 제공되어 참가자들이 대회에 집중할 수 있도록 최적의 환경을 제공한다. 그중 참가자들을 진정 열광시키는 것은 수많은 팀에게 추첨을 통해 문화상품권을 나눠준다는 점이다.
컴퓨터정보공학과에 재학 중인 강호는 대회에 참가하기 위해 팀원을 모집하려고 한다. IUPC가 여타 많은 대회와 다른 점이 있다면 문제의 수가 많고 팀원의 수가 무제한이라는 것이다. IUPC에서 모든 문제를 다 풀어 우승한 뒤 엄청난 부와 명예를 챙기고 싶은 강호는 모든 문제를 풀 수 있는 팀을 만들고 싶어 한다. 하지만 팀원의 수가 많으면 많을수록 자신에게 돌아오는 상금이 적어지기 때문에 최소한의 팀원으로 대회를 우승하고 싶어 한다.
강호가 선택할 수 있는 팀원의 목록과 각각의 팀원들이 해결할 수 있는 문제의 번호들이 주어졌을 때 강호가 IUPC에서 최소한의 팀원으로 모든 문제를 다 풀어 우승할 수 있도록 팀을 만들어보자.
입력
첫 번째 줄에 문제의 수 N과 강호가 팀원으로 고를 수 있는 학생들의 수 M이 공백을 구분으로 차례대로 주어진다. N과 M은 1이상 10이하의 자연수이다.
두 번째 줄부터 M개의 줄에 차례대로 i(1 ≤ i ≤ M)번 학생들이 풀 수 있는 문제의 개수 Oi와 i번 학생이 풀 수 있는 문제의 번호 Pij(1 ≤ j ≤ Oi, 1 ≤ Pij ≤ N)가 Oi개 주어진다.
출력
모든 문제를 풀 수 있으면서 팀원의 수가 가장 적은 팀을 구해 팀원의 수를 출력한다. 만약 모든 문제를 풀 수 있는 팀을 만들 수 없다면 -1을 출력한다,
풀이
N과 M의 범위가 너무나 자비롭다. 10명의 학생으로 팀을 구성할 수 있는 모든 경우의 수는 공집합을 제외하고 1023가지다. 그냥 다 돌려보면 답 나온다. 브루트포스로 갑시다.
재귀 함수를 구성해보자. 재귀를 구성할 때는 매개변수를 잘 정해야 한다. 다음 깊이의 탐색에 무엇을 넘길 것인가, 무엇을 반환 받을 것인가. 그리고 언제 탐색 깊이를 한 단계 더 내려갈 것인가, 언제 탈출할 것인가도 잘 생각해야 한다.
i번째 학생을 팀원으로 들인 경우, 다음 탐색에서 i + 1번째 학생부터 M번째 학생까지 돌아보며 팀원으로 영입해본다. 그리고 영입한 학생의 번호를 j라고 하자. 그러면 j번 학생이 풀 수 있는 문제들을 i번째 학생까지로 구성된 팀원이 풀 수 있는 문제와 합친다. 그리고 탐색은 다음 단계로 넘어간다.
새로운 탐색을 시작할 때는 지금까지 모인 팀원으로 풀 수 있는 문제들을 확인한다. 모든 문제를 풀 수 있다면 현재 탐색 깊이(= 지금까지 모인 팀원)를 확인하고 최소 팀원으로 기록한 뒤 탈출한다. 이어서 다음 가능한 경우를 계속 탐색해 나가는데 이제부터는 매 탐색마다 기존 최소 인원과 깊이를 비교해 더 깊이 탐색할 필요가 없다. 인원 수가 최소치보다 많아지면 해가 될 수 없기 때문이다.
정답 코드
import sys
input = sys.stdin.readline
def solution():
N, M = map(int, input().split())
can_solve = [list(map(int, input().split()))[1:] for _ in range(M)]
all_solve = (1 << N) - 1
def make_team(i, bit, n, rec):
if bit == all_solve:
return n
if n == rec:
return rec
for j in range(i + 1, M):
new_bit = bit
for p in can_solve[j]:
new_bit |= 1 << (p - 1)
rec = make_team(j, new_bit, n + 1, rec)
return rec
result = make_team(-1, 0, 0, M + 1)
if result > M: result = -1
print(result)
solution()