https://www.acmicpc.net/problem/1062
1062번: 가르침첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문www.acmicpc.net
거의 처음으로 풀어본 비트마스킹 문제였다.
생각보다 할만했다.
가장먼져, 무조건 포함되는 (a,n,t,i,c) 를 각각ord(‘a)를 빼줘 비트집합 must_have로 바꾼다
0b10000010000100000101 가 된다.
이후, 단어를 받을때마다 &를 통해 (a,n,t,i,c)를 제거한다.
그리고, 남아있는 단어들을 k-5개의 원소를 가지는 comb로 만들어서,
각각의 받은 단어와 &로 비교했을때 받은 단어가 나오면 읽을 수 있는것이다.
처음풀이해본거라 코드가 좀 난잡하다
import sysfrom itertools import combinationsinput=sys.stdin.readline
n,k=map(int,input().split())must_have=0comb=list(range(26))
for w in ('a','n','t','i','c'): bn=(ord(w)-ord('a')) must_have|=1<<bn
comb.remove(bn)word_list=[]for _ in range(n): tmp=0
wo=list(set(input().strip())) for w in wo: b= 1<<(ord(w)-ord('a'))
tmp |= b tmp&= ~(must_have) word_list.append(tmp)if k<5:
print(0) exit() teaches=combinations(comb,k-5)answer=0
for teach in teaches: tmp_answer=0 tmp=0 for t in teach:
tmp |= 1<<t for word in word_list: if (word&tmp)==word:
tmp_answer+=1 if tmp_answer>answer: answer=tmp_answer
print(answer)다른사람의 풀이를 보다가 시간이 엄청짧은 코드가 있길래 보니, 비트마스킹이 아닌
집합연산으로만 풀었다.
참고용#내풀이아님
##새로운사실: 집합의 비교연산자는 상위집합인지 아닌지를 비교!
from itertools import combinationsfrom sys import stdininput = stdin.readline
def solution(): n,k = map(int, input().split()) if k < 5: return 0
k -= 5 learned = set('antic') unlearned = set()
cant_read_words = [] can_read_cnt = 0 for _ in range(n):
word = set(input().rstrip()) - learned if word:
unlearned.update(word) cant_read_words.append(word)
else: can_read_cnt += 1 if len(unlearned) <= k:
return n answer = 0 for comb in combinations(unlearned,k):
comb = set(comb) cnt = 0 for word in cant_read_words:
if comb >= word: cnt += 1
answer = max(answer, cnt) answer += can_read_cnt return answer
print(solution())