문제 링크

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

문제 설명

• 문자열 리스트가 주어짐
• antatica를 무조건 포함
• 소문자 알파벳 중에서 k개를 선택해서 가르침
• 단어를 온전히 읽을 수 있는 개수의 최대값 출력

풀이

• antic를 미리 선택
• 나머지 중에서 k-5개 선택
• 선택한 알파벳으로 읽을 수 있는 단어 카운트
• 최댓값 출력

후기

• 처음에 복잡도 계산을 잘못해서 시간초과가 날 줄 알았다
• 문제 유형에 비트마스킹이 있어서 그쪽으로 생각해봤다
• 근데 antatica를 빼고 다시 계산해보니 모든 경우의 수를 세어도 40만 이하였다
• 완전탐색해보니 그냥 풀렸다

코드

import sys
from itertools import combinations

def solution():
    read = sys.stdin.readline
    n, k = map(int, read().split())
    words = [read().rstrip()[4:-4] for _ in range(n)]

    # antatica를 선택할수 없으면 0
    if k < 5:
        print(0)
        return

    already = set('antatica')

    chars = [chr(ord('a')+i) for i in range(26) if chr(ord('a')+i) not in already]
    max_count = float('-inf')

    # chars 중에서 k-5개 선택
    for combi in combinations(chars, k-5):
        sett = already | set(combi)
        count = 0
        for word in words:
            possible = True
            # words 중에 하나라도 불가능하면 break
            for i in range(len(word)):
                if word[i] not in sett:
                    possible = False
                    break
            if possible:
                count += 1
        max_count = max(max_count, count)
    print(max_count)

solution()