백준 1062: 가르침

import sys, itertools

# n, m 입력
n,m = map(int, sys.stdin.readline().split())

# words : 각 단어의 비트마스킹한 정수를 저장
words = [0] * n
ans = 0
for i in range(n):
    temp = sys.stdin.readline().rstrip()
    # word 배열에 각 문자의 비트마스킹 저장
    for x in temp:
        words[i] |= (1 << (ord(x) - ord('a')))
        
# 만일 m이 5미만이면 필수 글자를 다 배울 수 없기 때문에 한 단어도 읽지 못한다
if m < 5:
    print(0)
else:
    # candidiate : 필수 글자를 제외한 알파벳
    # need : 필수 알파벳
    candidiate = ['b','d','e','f','g','h','j','k','l','m','o','p','q','r','s','u','v','w','x','y','z']
    need = ['a','c','t','i','n']
    for i in list(itertools.combinations(candidiate, m - 5)):
        each = 0
        res = 0
        # 각 조합에 대한 비트마스킹
        for j in need:
            each |= (1 << (ord(j) - ord('a')))
        for j in i:
            each |= (1 << (ord(j) - ord('a')))
            
        # 단어와 각 조합의 비교
        for j in words:
            if each & j == j:
                res += 1
                
        # 최대값 갱신
        if ans < res:
            ans = res
    print(ans)

접근 방식

![]

비트 마스킹

후기

완전탐색, 비트마스킹을 통한 문자열 비교

• anta/tica 에서 a, n, t, i, c 5개의 글자는 무조건 학습해야 학습이 가능하므로, 민수가 학습 시킬 글자 개수 K는 K - 5 로 변경해야 한다.
• 비트마스킹을 이용하면, 어떤 문자의 부분집합을 하나의 정수로 나타낼 수 있고, 부분집합의 비교를 AND 연산을 통한 정수 비교를 하기 때문에 비교가 빨라진다.
• k-5개 만큼의 학습이 가능하다는 것과 조합까지는 생각했는데 비트 마스킹은 생각하지 못했다.
• 역시 골드는 어렵다

풀이 참고

1062 : 가르침