https://www.acmicpc.net/problem/1062
문제
코드
from itertools import combinations
def find(base, arr):
cnt = 0
for i in arr:
if (base & i) == i:
cnt += 1
return cnt
n, k = map(int, input().split())
t = []
v = set()
k -= 5
for _ in range(n):
s = input().strip()
r = 0
for i in s:
if i in 'acint': continue
v.add(1 << ord(i) - 97)
r |= (1 << ord(i) - 97)
t.append(r)
if k < 0:
print(0)
else:
ans = 0
for comb in combinations(v, min(k, len(v))):
base = 0
for c in comb:
base += c
ans = max(ans, find(base, t))
print(ans)
Idea 1
for i in s:
if i in 'acint': continue # 'acint'가 포함된 경우는 확인하지 않음
v.add(1 << ord(i) - 97) # 사용되는 문자를 하나씩 저장하는 집합(set)
r |= (1 << ord(i) - 97) # 비트 OR연산을 통해 사용되는 문자 전체 저장
Idea 2
combinations(v, k) -> 오류
combinations(v, min(k, len(v))) # 조합(문자 집합, 최소값(사용할 수 있는 문자 개수, 문자 집합의 길이(개수))
-> 사용할 수 있는 문자(k)는 20개 이지만 집합에는 2개의 문자(len(v))만 포함되어 있다면 오류가 발생
++ 문제를 풀때는 생각이 잘 안났는데 다시 보니 너무 당연한 것 같네.. 집합 길이보다 선택개수가 크면 어떻게 뽑겠니? 어?
