[백준][PyPy3] 1062번 가르침 - 코팩

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

1062번: 가르침

풀이

기본적으로 가르쳐야할 알파벳은 남극의 기본문법인 "a", "c", "i", "t", "n" 총 5개이다.

(위의 5개의 알파벳을 가르치지 않으면 어떠한 단어도 읽을 수 없다.)

 

combinations로 조합을 통해 추가로 가르칠 알파벳을 골라주었다.

 

이를 통해서 완전탐색으로 단어를 읽을 수 있는지 없는지 확인해주었다.

 

시간초과 문제로 인해 PyPy3로 제출해주었습니다.

 

코드(PyPy3)

# 1062번 가르침
import sys
from itertools import combinations
input = sys.stdin.readline

n, k = map(int, input().split())
words = [sys.stdin.readline().rstrip() for _ in range(n)]

basic = set(["a", "c", "i", "t", "n"])
unlearned = set(chr(i+ord("a")) for i in range(26)) - basic
ans = 0

learned = [0] * 26
for i in basic:
    learned[ord(i)-ord("a")] = 1
    
def count_words(li):
    cnt = 0
    learned = li
    for word in words:
        flag = True
        for i in word:
            if learned[ord(i)-ord("a")] == 0:
                flag = False
                break
        if flag:
            cnt += 1
    return cnt
            

if k < 5:
    print(0)
else:           
    for new_word in combinations(unlearned, k-5):
        for i in new_word:
            learned[ord(i)-ord("a")] = 1
        ans = max(ans, count_words(learned))
        for i in new_word:
            learned[ord(i)-ord("a")] = 0
    print(ans)

 

출력결과