문제링크

1062 - 가르침

문제설명

주어지는 모든 단어 N개는 "anta"로 시작되고, "tica"로 끝난다. K개의 글자로 이루어진 단어만 읽을 수 있을때, 읽을 수 있는 단어의 개수가 최대가 되게끔 K를 설정한다. 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

문제풀이

시도 1 브루트포스

import sys
from collections import defaultdict
from itertools import combinations

input = sys.stdin.readline

N, K = map(int, input().split())
words = []
alph = set()
readable = ['a', 'n', 't', 'i', 'c']

for _ in range(N):
    words.append(list(input().strip()))
    # N개의 단어 중 ['a', 'n', 't', 'i', 'c']에 포함되지 않는 알파벳 저장
    for w in words[-1][4:-4]:
        if w not in readable:
            alph.add(w)

if K < 5:
    print(0)
    sys.exit(0)

K -= 5

# 읽어야 하는 단어가 K보다 작거나 같으면 모든 단어 읽을 수 있음
if len(alph) <= K:
    print(len(words))
    sys.exit(0)
else:
    pos = combinations(alph, K)

answer = 0
for p in pos:
    count = 0
    for word in words:
        flag = True
        for w in word[4:-4]:
            if w not in readable and w not in p:
                flag = False
                break
        if flag == True:
            count += 1
    answer = max(answer, count)

print(answer)

시도 2 비트마스킹