[비트마스킹/ 파이썬 ] 백준 1062번 : 가르침 / 골드 4

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

import sys

sys.setrecursionlimit(10 ** 5)

n, k = map(int, input().split())

if k < 5:
    print(0)
    quit()
    
must = 0
for alpha in 'antic':
    order = ord(alpha) - ord('a')
    must |= 1 << order

words = []
for _ in range(n):
    word = input()
    b = 0
    for alpha in word:
        order = ord(alpha) - ord('a')
        b |= 1 << order
    words.append(b)


def check(learn):
    read = 0
    for j in range(n):
        word = words[j]
        if (learn & word) == word:
            read += 1
    return read


def recursion(idx, learn):
    global answer
    if idx > 26:
        return

    if bin(learn).count('1') == k:
        answer = max(answer, check(learn))
        return

    if must & (1 << idx):
        recursion(idx + 1, learn | (1 << idx))
    else:
        recursion(idx + 1, learn)
        recursion(idx + 1, learn | (1 << idx))


answer = 0
recursion(0, 0)
print(answer)

 

<사용한 비트 연산>

 

1. order 위치에 비트 1 추가

b |= 1 << order

 

2. learn이 word의 비트를 포함하는 지 여부

if (learn & word) == word:

 

3. must의 특정 위치의 비트가 1인지 여부

if must & (1 << idx):