[Python3] 백준 - 9997 폰트

www.acmicpc.net/problem/9997

9997번: 폰트

- 접근법

N이 25이므로 브루트포스로 모든 단어를 조합해도 O(2^25)로 가능하다.

그러나 탐색과 연산횟수도 합해진다면 O(2^25*alpha)로 TLE가 날수있으므로 가지치기를 잘해줘야한다.

 

사실 이 문제는 비트마스킹으로 해당 알파벳이 존재하면 TRUE, 안하면 FALSE같이 저장해서 간단히 비트연산으로 알파벳 26개 다 존재하는지 볼 수 있다.

하지만 나는 당시에 파이썬으로 비트마스킹하는법을 몰라서 처음에 단어들을 받을때 먼저 set화 시켜놓고 set끼리의 연산으로 비트마스킹을 흉내냈는데 빠른 시간에 accept되는것을 보니 set연산은 시간을 많이 잡아먹진 않는 것 같다. 

 

따라서 다시 이 문제를 요약하자면

"각 단어들을 (사용해서 문장에 붙일 때, 안 붙일 때)로 탐색하면서 현재 문장이 a부터z까지 모든 요소가 있는지 검사만 해주면 된다."

"index 끝까지 탐색하고 검사하는 것보다는, 성능을 더 올리기 위해 가지치기를 해주자"

 

---

- 소스코드

import sys
input=sys.stdin.readline
global answer
answer=0
def word_combine(vertex,sentence) :
    if len(sentence) == 26:
        global answer
        answer += 2 ** (N - vertex-1)
        return
    if vertex>=0 and len(sentence)+word_len[vertex]<26 :
        return
    if vertex==N-1 :
        return
    word_combine(vertex+1,sentence|word_list[vertex])
    word_combine(vertex+1,sentence)
 
N=int(input().rstrip())
word_list=[set(input().rstrip()) for x in range(N)]
word_len=[len(sets) for sets in word_list]
for i in range(N-2,-1,-1) :
    word_len[i]+=word_len[i+1]
word_combine(-1,set())
print(answer)