문제

• 
• 시간 제한: 1초
• 메모리 제한: 128MB

Problem Analysis

소문자 26개 중에 무작위로 k 개를 선택하는 모든 경우를 조사하는 방법밖에 없다.

Algorithm

k 개를 가르칠 때까지, 다음과 같이 Backtracking을 하여 최대를 구한다.

• 현재 글자를 가르친다. 다음 글자로 Recursive call
• 현재 글자를 가르치지 않는다. 다음 글자로 Recursive call
  (각 0부터 25번에 해당하는 bit에 a~z에 대한 flag를 저장한다)

k 개에 도달했을 때, 다음과 같이 읽을 수 있는 단어를 계산하여 return 한다.
count += (각 단어|flags) == flags

Data Structure

• words_flags[N]: 각 단어가 가지는 알파벳 flags를 저장
• flags: 현재 가르친 flags를 저장

이때, flags는 int에 저장. (32bits이므로, 26가지 글자를 표현 가능)

결과

Other

시간 복잡도는 O( c(26,k) ) 이다.
a, n, t, i, c은 필수적으로 있어야 한다.
이것을 미리 넣어두면 경우의 수를 많이 줄일 수 있는데, 결과에서도 확인할 수 있다.