import sys
input = sys.stdin.readline
def count(last,bit):
global cnt
if bit+1 == 1<<26:
cnt += 2**(N-last-1)
return
for i in range(last+1,N):
count(i,bit|bitlist[i])
N = int(input())
bitlist = [0]*N
for i in range(N):
word = input().strip()
for w in word:
bitlist[i] |= (1<<ord(w)-97)
cnt = 0
count(-1,0)
print(cnt)브루트포스+비트마스킹을 이용해서 문제를 해결하였다.
알고리즘을 요약하면
1. 각 단어가 가지고 있는 알파벳의 집합을 비트마스킹으로 저장한다.
2. 브루트포스 방식으로 비트 합집합 연산을 하면서 문장을 늘려간다.
3. 모든 알파벳이 문장 안에 들어갔으면, 현재까지 본 단어를 제외한 나머지 단어들의 경우의 수만큼 세어준다. (포함되고, 안되고 두가지이므로 2^n(n은 남은 단어의 개수)이다)
비트마스킹 한번 배워놓으면 여러모로 유용한 알고리즘이라는 생각이 든다.
오늘의 교훈) 비트마스킹을 적절하게 활용하자