백준 1062 파이썬 - 가르침

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

1062번: 가르침

문제

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

코드

import sys
n, k = map(int, sys.stdin.readline().split())
if k < 5 or k == 26:
    print(0 if k < 5 else n)
    exit()
arr = [set(sys.stdin.readline().rstrip()) for _ in range(n)]
array = [0] * 26
for i in ('a', 'c', 'i', 'n', 't'):
    array[ord(i) - ord('a')] = 1
answer = 0
def dfs(i, count):
    global answer
    if count == k - 5:
        temp = 0
        for word in arr:
            for w in word:
                if not array[ord(w) - ord('a')]:
                    break
            else:
                temp += 1
        answer = max(answer, temp) if answer else temp
        return
    for j in range(i, 26):
        if not array[j]:
            array[j] = 1
            dfs(j, count + 1)
            array[j] = 0
dfs(0, 0)
print(answer)

풀이

pypy로 제출했다. set을 활용해 중복인 알파벳을 없앴다. k - 5는 모든 단어에 공통되는a,c,i,n,t를 빼준 것이다. 이것이 count와 같으면 모든 단어를 탐색해 읽을 수 있으면 answer를 조건문을 통해 갱신해준다. 끝으로 answer를 출력하면 된다.