[백준] 1062번 가르침 - 파이썬/백트래킹, 비트마스킹

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

1차 풀이

import sys

N,K = map(int,sys.stdin.readline().split())
word_list = []
set_word = []
for i in range(N):
    word = sys.stdin.readline().rstrip()
    word_list.append(word)
    set_word.append(set(list(word)))

anta = ['a', 'c', 'i', 'n', 't']
anta_set = set(anta)
all_ap = list(set(list(''.join(word_list))) - anta_set)
all_ap.sort()
check = len(all_ap)
array = ['a', 'c', 'i', 'n', 't']

max_cnt = -999999
# anta, tica = ['a', 'c', 'i', 'n', 't']

def dfs(depth,K,idx):
    global max_cnt
    if depth==K-5:
        cnt = 0
        for w in set_word:
            if w <= set(array):
                cnt+=1

        if cnt >= max_cnt:
            max_cnt = cnt

        return

    for i in range(idx,check):
        array.append(all_ap[i])
        dfs(depth+1,K,i+1)
        array.pop()

if K<5:
    print(0)

elif K==26:
    print(N)
else:
    dfs(0,K,0)
    print(max_cnt)

정답은 나오는데 시간초과가 발생했다.

2차 풀이

import sys

N,K = map(int,sys.stdin.readline().split())
word_list = []
set_word = []
for i in range(N):
    word_input = sys.stdin.readline().rstrip()
    set_word.append(set(list(word_input)))

learn = [0]*26

for c in ('a', 'c', 'i', 'n', 't'):
    learn[ord(c) - ord('a')] = 1


answer = 0

def dfs(idx, cnt):
    global answer

    if cnt == K - 5:
        readcnt = 0
        for word in set_word:
            check = True
            for w in word:
                if not learn[ord(w) - ord('a')]:
                    check = False
                    break
            if check:
                readcnt += 1
        answer = max(answer, readcnt)
        return

    for i in range(idx, 26):
        if not learn[i]:
            learn[i] = True
            dfs(i, cnt + 1)
            learn[i] = False

if K<5:
    print(0)

elif K==26:
    print(N)
else:
    dfs(0,0)
    print(answer)

비트마스킹 개념을 도입해서 시간복잡도를 줄였다.