1062 가르침

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

#백트래킹

#비트마스킹

#itertools combinations

1062번: 가르침

#내 코드

#1062 가르침 정리
from sys import stdin
#standard input

 

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

#n,k 입력

 

word_list=[input().strip() for i in range(n)]
set_word_list=[]
alpha_set=set([])
for i in word_list:
    set_word_list.append(set(i))
    alpha_set|=set(i)

#집합을 이용해서 중복을 제거해준 뒤에 alphabet만 있는 집합과 집합으로된 단어를 담은 리스트를 저장해준다.

alpha=[False for i in range(26)]
#각 알파벳을 담을 리스트

if k>=len(alpha_set):

    print(n)
#k가 알파벳의 수보다 크거나 같으면 모든 단어 가능

     
elif k<5:
    print(0)

#5보다 작으면 단어를 읽지 못함

else:
#이 모든 것이 아니라면
    answer=0

    def backtracking(index,count):
        global answer
        if count==0:
            result=0
            for word in word_list:
                for w in word:
                    if not alpha[ord(w)-ord('a')]:
                        break

                else:
                    result+=1
            answer=max(answer,result)

#count가 0이 된다면 (조건) 단어를 하나씩 해체해서 alpha리스트와 비교

        else:
            for i in range(index,26):
                if alpha[i]==False:
                    alpha[i]=True
                    backtracking(index+1,count-1)
                    alpha[i]=False

#조합

    for i in ['a','n','t','i','c']:
        alpha[ord(i)-ord('a')]=True
#antic 빼주고
    backtracking(0,k-5)
#돌리기
    print(answer)

 

#비트마스킹을 이용한 답지 코드

from itertools import combinations
#집합을 열수도 있으나 함수 이용하자

n,k=map(int,input().split())
#n,k 입력
if k<5 or k>=26:
#5보다 작거나 26 보다 크면
    print(0 if k<5 else n)
#0이거나 n
else:
#모든것이 아니라면
    answer=0
#결과 값
    k-=5
#k를 미리 빼준다
    learned={'a','n','t','i','c'}
#알아야 할 것들
    words=[]
#단어 리스트
    alpha_list={key:value for value,key in enumerate(set(map(chr,range(ord('a'),ord('z')+1)))-learned)}
#각각 알파벳:인덱스값 이런식으로 저장되는데 여기서 antic는 빠져있다.
    for _ in range(n):
        tmp=0

        for c in set(input())-learned:
            tmp|=(1<<alpha_list[c])
        words.append(tmp)

#단어를 각각 입력 받고 해체해서 알파벳을 tmp에 저장 alpha_list에 의해서 list처럼 사용됨 1<<? 는 2**?이라고 생각하#면 됨 !bit shift! 받은 숫자 ( 단어) 를 words 에 저장

    power2=[2**i for i in range(21)]

#비트로 표현됐으니 똑같이 power 만들어줌 power는 제곱 power by 2 2의 제곱
    for comb in combinations(power2,k):
        test=sum(comb)
        ct=0
        for word in words:
            if test&word==word:
                ct+=1
        answer=max(answer,ct)
    print(answer)

#제일 중요한 건 & 이거다 &는 두개의 비트를 and처리해준다 고로 같아야 된다 if절의 뜻은 word와 test의 공통공간이 #word일때 word가 test에 들어갈 때 ct를 더하라는 것이다.

 

#비트 마스킹에 대해서 배우게 된 파트 어렵다