백준: 1062 가르침

문제

1062번: 가르침

 

문제 풀이

 학생들은 K개의 알파벳을 배울 수 있다. 이때 N개의 단어 중 가장 많은 단어를 읽을 수 있는 경우의 수를 찾는 문제이다. 문제는 다음과 같은 경우를 확인하며 DFS로 풀면 쉽게 풀 수 있다.

 

• 언어는"anta"로 시작되고, "tica"로 끝나므로 배울 수 있는 단어 중, 'a', 'c', 'i', 'n', 't'를 배워야 하므로 5를 제외한다.
  • 만약 K가 5보다 작다면, 읽을 수 있는 단어는 없다.
  • K가 26이라면 모든 알파벳을 배울 수 있으므로 주어진 단어 N을 다 읽을 수 있다.
• DFS는 백트랙킹을 통해, a ~ z 중 K - 5 만큼 배운 후 몇 개의 단어를 읽을 수 있는지 확인한다.

 

코드

from sys import stdin, exit


def dfs(idx, cnt):
    global answer

    if cnt == k - 5:
        read_cnt = 0
        for word in words:
            for w in word:
                if not learn[ord(w) - ord('a')]:
                    break
            else:
                read_cnt += 1
        answer = max(answer, read_cnt) if answer else read_cnt
        return

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


if __name__ == '__main__':
    answer = None
    n, k = map(int, stdin.readline().split())

    if k < 5 or k == 26:
        print(0 if k < 5 else n)
        exit(0)

    words = [set(stdin.readline().rstrip()) for _ in range(n)]
    learn = [False] * 26

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

    dfs(0, 0)
    print(answer)

 초기에 단어를 입력 받을 때, 중복되는 알파벳이 있다면 탐색의 오버헤드만 증가시키므로 set()을 이용하여 단어 중 중복된 알파벳이 없도록 하였다. 파이썬으로는 해당 코드로 시간 초과가 발생하며, PyPy3로 제출할 경우 시간 내에 정답을 반영할 수 있다.