[비트마스킹] 백준 1062 가르침

문제링크 https://www.acmicpc.net/problem/1062

 

 

1. set()은 문자열로 넣어도 원소 하나하나로 접근한다는 점

2. combination에 현재 list 길이보다 큰 값이 들어오면 combination 함수가 돌아가지 않는다는 점

3. set() 연산 : |= 합집합, - 차집합

을 배웠다.

 

 

[답코드]

import sys
from itertools import combinations
 
input = sys.stdin.readline
n, k = map(int, input().split())
 
k -= 5
if k < 0:
    print(0)
else:
    word, bits, basecom = [], [], set()
    bit = {chr(ord('a') + i): 1 << i for i in range(26)}
    baseword = set('antic')
 
    for _ in range(n):
        word = set(input().strip()) - baseword  # 빼기
        basecom |= word  # 더하기
        tmp = 0
        for w in word:
            tmp += bit[w]
        bits.append(tmp)
 
    # bits, com
    ret=0
    for co in combinations(basecom, min(k, len(basecom))):
        tmp = 0
        for c in co:
            tmp += bit[c]
 
        cnt=0
        for b in bits:
            if tmp & b == b:
                cnt+=1
        ret=max(ret, cnt)
 
    print(ret)
 
 
 

 

[반례]

 

2 7
antatica
antaktica

 

답 : 2