문제
N개의 기타가 각각 M곡 중 일부를 연주할 수 있다. 가장 많은 곡을 연주할 수 있는 기타 조합 중 기타 수가 최소인 것을 구하라.
입력
첫째 줄에 기타 수 N과 곡 수 M, 이후 N줄에 기타 이름과 Y/N 문자열이 주어진다.
출력
최소 기타 수를 출력한다. 아무 곡도 연주할 수 없으면 -1을 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 5 a YYYYY b YYYYY c NNNNN | 1 |
풀이
각 기타의 연주 가능 곡을 비트마스크로 변환한 뒤, 모든 부분집합의 OR 결과로 최대 곡 수와 최소 기타 수를 구한다.
- Y/N 문자열을 이진수로 변환하여 각 기타의 비트마스크를 만든다
- 1부터 2^N-1까지 모든 부분집합을 순회한다
- 선택된 기타들의 OR 결과에서 1의 개수(연주 가능 곡 수)와 기타 수를 구한다
- 최대 곡 수를 갱신하고, 같은 곡 수에서 기타 수가 더 적으면 갱신한다
핵심 아이디어: N이 최대 10이므로 2^10 = 1024개의 부분집합만 확인하면 된다. 비트 OR로 곡 합집합을 O(1)에 계산한다.
코드
import sys
n, m = map(int, input().split(" "))
min_g = n + 1
max_s = 0
l = []
for i in range(n):
guiter, able = sys.stdin.readline().rstrip().split(" ")
able = able.replace("Y", "1")
able = able.replace("N", "0")
l.append(int(able, 2))
for i in range(1 << n):
n_guitar = 0
check = 0
for j in range(n):
if i & (1 << j):
a = l[j]
check = check | a
n_guitar += 1
if max_s < bin(check).count("1"):
min_g = n_guitar
max_s = bin(check).count("1")
elif max_s == bin(check).count("1"):
if min_g > n_guitar:
min_g = n_guitar
if max_s == 0:
print(-1)
else:
print(min_g)복잡도
- 시간: O(2^N * N)
- 공간: O(N)