[백준] [Python] #1062 가르침

https://www.acmicpc.net/problem/1062

1062번: 가르침

다들 비트마스킹으로 푸는걸 나는 set으로 풀기 시도를 했다.

뭔가 아이디어는 이게 맞는거같은데 주어진 테스트케이스 중 세번째에서 오답이 나와서 때려쳤다...

아래 코드는 때려치기 직전의 오답 코드이다...

n, k = map(int, input().split())

if k-5 <= 0 : 
    print(0)
    exit()

voca = []
for _ in range(n): voca.append(input()[4:-4])
str = ''
vocaNeed, vocaList = {}, {}
ans, tmp = 0, 0

vocaDefault = {'a', 'n', 't', 'i', 'c'}

for v in voca:
    str += v
vocaNeed =  set(str) - vocaDefault

import itertools
ncr = itertools.combinations(vocaNeed,k-5)
for c in ncr:
    tmp = 0
    vocaList = set(c) | vocaDefault
    for v in voca: 
        if (vocaList - set(v)) : tmp += 1
    if tmp > ans: ans = tmp

print(ans)

혹시 몰라 제출도 해봤는데 역시나 였다. 결론은 비트마스킹으로 풀어라!!!

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)

 

 

참고1 : https://oranz.tistory.com/38

참고2 : https://dallae7.tistory.com/134