[python] 백준 1062 가르침

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

1062번: 가르침

문제해결

• anta와 tica 사이 알파벳을 봐야하지만 중요한 것은 'a', 'n', 't', 'i', 'c' 는 무조건 들어가야한다.
• 즉 k<5이면 무조건 정답은 0이다.
• 전체 알파벳중에서 'a', 'n', 't', 'i', 'c'를 제외한 나머지 알파벳중 k-5개를 고른 후 그 알파벳으로 만들 수 있는 단어의 개수를 확인 하는 방법 밖에는 없다.
• 확인 하는 방법은 ord 함수를 이용해서 주어진 리스트에 ord('x')인덱스의 존재 유무(1/0)을 보고 확인하는 것이다.(이는 비트마스킹 개념과 유사하다.)

 

CODE

from itertools import combinations
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
answer = 0
res = set(chr(i) for i in range(97,123))-{'a','n','t','i','c'}
data = []
for _ in range(n):
    word = str(input().rstrip('\n'))
    data.append(word[4:-4])

def solve(data,learned):
    cnt = 0
    for word in data:
        canRead = 1
        for w in word:
            if learned[ord(w)] ==0:
                canRead=0
                break
        if canRead:
            cnt += 1
    return cnt

if k>=5:
    learned = [0]*123
    for x in {'a','n','t','i','c'}:
        learned[ord(x)] = 1
    
    for teach in list(combinations(res,k-5)):
        for t in teach:
            learned[ord(t)] = 1
        cnt = solve(data,learned)
        if cnt > answer:
            answer = cnt
        for t in teach:
            learned[ord(t)] = 0
    print(answer)
else:
    print(0)