[백준 1062] 가르침

https://www.acmicpc.net/problem/1062 문제이해 단어의 개수 N과 학생들이 읽을 수 있는 글자의 개수 K가 주어졌을 때 학생들이 읽을 수 있는 단어 개수의 최대값을 구하라. 여기서 단어들은 모두 anta로 시작하고 tica로 끝나기 때문에 a, n, t, i, c의 총 5개 글자는 알고 있어야 한 단어라도 이해할 수 있다 그렇지 않은 경우 출력은 무조건 0 풀이 antarctica antahellotica antacartica 의 경우 (a, n, t, i, c)를 제외한 (r, h, e, l, o)의 글자를 추가적으로 알아야 단어를 이해할 수 있다.

그래서 처음으로는 (r, h, e, l, o)에서 선택할 수 있는 글자의 개수만큼의 조합을 구하고 각 단어의 글자를 하나씩 확인하는 방법으로 문제를 풀었다. 그렇게 하니 결국 최악의 경우 21C10 * 50 * 7을 했을 때 122,500,000의 연산이 필요해 시간 초과가 났다.

여기서 비트 마스크를 활용해...