BOJ 1062 가르침

"anta"로 시작해 "tica"로 끝나는 N개의 단어가 주어지고 k가 주어지는데, (k개의 글자를 잘 선택해서) k개의 글자(알파벳)만으로 구성된 단어의 최대 개수를 구해야 한다.

일단 "anta"와 "tica"가 포함된 단어를 읽기 위해서는 a, c, i, n, t 이렇게 5개의 글자가 필요하다. 저 5개의 글자는 반드시 필요하다. 그렇기 때문에 k가 5보다 작으면 읽을 수 있는 단어의 개수는 0이다.

N제한이 50이고, 단어의 길이도 최대 15이므로 일일이 다 보면 될 것 같다. 구현이 쉬워보이지는 않지만... 구현해 봐야겠다.

일단 체크배열을 이용해서 각 단어마다 어떤 글자가 필요한지 기록을 했다.
그리고 이제 어떻게 할 것인가? 음... 가장 많이 겹치는 글자를 우선적으로 선택해서는 최대값을 얻을 수 없다. 왜냐하면 abcd, abc, acd, x, y 이렇게 5개의 단어가 있다고 하면 k=2일 때, x, y를 k개의 글자로 선택해야 읽을 수 있는 단어가 x, y 2개로 최대가 된다.
많이 겹쳐도 결국 단어를 읽으려면 단어가 포함하는 모든 글자가 필요하기 때문이다...

결국 모든 가능한 경우를 다 해보는 것이 가장 먼저 떠오르는 방법이다. 너무 경우의 수가 많지 않을까 하는 생각이 들긴하지만 생각해보면 그렇지도 않다.
일단 어떤 모든 가능한 경우를 다 해볼 것인가?
주어진 k의 수대로 가능한 모든 경우의 k글자를 정한 후 몇개의 단어를 읽을 수 있는지 비교해본다. k글자 정하는 경우의 수가 매우 많아 보이는데, 다행히 순열은 아니다. 그냥 고르는 것이기 때문에 조합이 될 것이다. 최대한 줄이기 위해서 문제를 잘 읽어보면 "anta"와 "tica"는 양 끝에 항상 포함되어있다. 그렇기 때문에 a, c, i, n, t이 5개의 글자는 반드시 필요하다.5이상의 k가 주어지면 일단 k-5에 대해서만 보면 되고, 주어진 단어들은 미리 비교하기 편하게 앞, 뒤 "anta"와 "tica"를 빼버리자.

이렇게 되면 알파벳 소문자 숫자는 최대 26이었는데 a, c, i, n, t 5 글자를 빼면 21개의 글자 중에서만 고르면 된다. k글자의 가능한 모든 경우의 수는 최대 21 C (k-5) 가 될 것이다.
시간 제한안에는 충분히 들어올 수 있을 것 같긴하다.
근데 21 C (k-5)의 경우의 수를 구현하는 것이 어려워보인다... 음 일단 문제 분류를 한 번 봐야겠다. 헉 보니까 문자열 처리, 시뮬레이션, 부르트포스... 내가 생각한 방식이 맞을 수도 있겠다.

일단 넘기고 다른 문제를 살펴봐야겟다.