[Python] 백준 <1062-가르침>

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

 

- pypy3로 통과

import sys
input = sys.stdin.readline

# 배울 수 있는 경우의 수 다 구하고 
# 각 경우의 수가 완성되면 배울 수 있는 단어 개수 비교
# n으로 글자수 카운트
def dfs(x, n):
    global dap
    if n == K:
        cnt = 0
        for i in li:
            boo = True
            for j in i:
                # 배우지 않은 글자가 포함이면 False
                if visited[ord(j)-ord('a')] == 0:
                    boo = False
            # 모두 배운 글자면 카운트
            if boo:
                cnt += 1
        # 배울 수 있는 단어의 최대값 구하기
        dap = max(dap, cnt)
    
    # 글자수 K개 맞추기
    # visited에 방문처리하고 비교한뒤 다시 방문 취소
    for i in range(x, 26):
        # 방문하지 않았으면 방문 처리
        if visited[i] == 0:
            visited[i] = 1
            # 방문 처리하고 개수에 따라 dfs 수행
            dfs(i, n+1)
            # 비교가 끝나면 해당 글자 방문 취소하고 다시 방문할 수 있게 함
            visited[i] = 0

N, K = map(int, input().split(" "))
li = list()
for _ in range(N):
    li.append(set(input().strip()))

word = ['a', 'n', 't', 'i', 'c']
if len(word) > K:
    print(0)
elif K == 26:
    print(N)
else:
    visited = [0]*26
    # 5개 글자 방문 처리
    for i in word:
        visited[ord(i)-ord('a')] = 1
    
    num = 5
    dap = 0
    # dfs 수행
    dfs(0, num)
    print(dap)