본문 바로가기

카테고리 없음

[백준 9997번] 폰트 (Python3)

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은 남은 단어의 개수)이다)

 

비트마스킹 한번 배워놓으면 여러모로 유용한 알고리즘이라는 생각이 든다.

 

오늘의 교훈) 비트마스킹을 적절하게 활용하자