[백준] 가르침

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

1062번: 가르침

 

combinations 을 직접 구현해보았고 구한 candidate 배열과 words 배열의 단어랑 비교하여 읽을 수 있는 단어를 찾는 것을 빠르게 구하는 게 중요했다. 우선, 'a', 'c', 'i', 'n', 't' 는 모든 단어마다 있으므로 K - 5 가 음수면 0을 출력해야 하며, K 가 26이면 모든 N개의 단어를 읽을 수 있으므로 N을 출력해주면 된다.

 

dictionary 를 이용하여 배운 K개의 글자에 대해서 1로 저장하여 읽을 수 없는 글자에 대해서 break 로 바로 다음 순서로 넘어가게 하였다. 해당 단어를 읽을 수 있다면 temp 에 1을 더하여 answer 을 temp 중 가장 큰 값으로 만들어 준다.

 

import sys
from collections import defaultdict

N, K = map(int, sys.stdin.readline().split())
acint = {'a', 'c', 'i', 'n', 't'}
words = [set(sys.stdin.readline().strip()[4:-4]) - acint for i in range(N)]
alphabet = list('bdefghjklmopqrsuvwxyz')
candidate = defaultdict(int)
K -= 5
start = 0
end = K
answer = 0

def combinations(alphabet, start, end, candidate):
    global K
    global words
    global answer

    if end == 0:
        temp = 0

        for word in words:
            for w in word:
                if candidate[w] == 0:
                    break
            else:
                temp += 1

        answer = max(answer, temp)

    else:
        for i in range(start, len(alphabet)-end+1):
            candidate[alphabet[i]] = 1
            combinations(alphabet, i+1, end-1, candidate)
            candidate[alphabet[i]] = 0

if K < 0:
    print(0)
else:
    if K == 21:
        print(N)
    else:
        combinations(alphabet, start, end, candidate)
        print(answer)