비트마스킹. [1062]

[1. 문제 설명]

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

---

[2. 풀이 접근]

단어를 읽기 위해서는 적어도 a,n,t,i,c 총 5개의 문자는 가르쳐야 한다.
즉, k-5 개를 가르쳐서, 읽을 수 있는 단어 개수를 최대로 해야한다.

 

단어에 나오는 문자 위주로 탐색해본다.

 

z 를 포함하는 단어가 없다면, 굳이 z 를 가르칠 필요는 없다.
또, 가장 많이 나오는 문자를 가르쳐서는 안된다.

• zb
• q
• zb 

일 때, 한 문자만 가르칠 수 있다면, q를 선택하는게 더 낫다.

조건 중, 단어의 길이는 최대 15
이 중, 5개 문자가 필수 이므로, 최대 10
10개중 선택할 수 있는 경우의 수 중 최대는 대략 10 combination 5

 

현실적인 시간 내에 모든 경우를 확인 해볼 수 있다.

따라서 완전 탐색으로 진행하도록 한다.

---

[3. 코드]