최악의 경우에는 (26-5)C10 = 352,716인데요.

백트래킹 해도 100ms 안에 나오는데. 안 나오시는 경우에는 다른 문제가 있으실 거 같네요.

예를 들어서, 시간 복잡도 앞에, 문자열 길이만큼이 곱해진다던지..

거기에 set을 초기화 하기 위해서 memset류 함수를 호출하시거나 하면. 26도 곱해지시겠죠.

음.. 혹시

특정 알파벳만을 배웠을 때, 이 단어를 읽을 수 있느냐. 없느냐를 어떻게 검사하셨나요?

예를 들어서 ANTAXYTNMOOTICA라는 단어가 있습니다.

학생들이 ACINTXZ를 배웠습니다. 이 경우에, ANTAXYTNMOOTICA라는 단어를 학생들이 읽을 수 있느냐 없느냐를

어떻게 검사하셨나요?

단어 읽는게 가능한지 여부는 비트연산으로 처리했습니다.

어디에서 문제가 생긴걸까요?

필요 없는 경우까지 백트래킹을 하는 게 문젠거 같네요.

실제로 아래와 같은 데이터를 주는 경우에

2600번이 21번째 줄 if문에 걸립니다. 2600이라.. 어떻게 나온 것일까요?

K는 8이였고요. 5를 빼서 3이 되었습니다.

26개 중에서, 서로 다른 3개를 택하는 가짓수는 26C3 = 26*25*24/6 = 2600이 나옵니다.

분명한 건

ant

act

와 같은 것도 탐사했다는 거고요. 답은 맞게 나왔습니다.

이건 이미, acint를 set에서 빼 놓았기 때문이지요. 다만. 백트래킹 과정에서 a, c, i, n, t를 거르지 못했다는 게 문제겠지요.

이들을 포함하는 sub는 보나 마나 없을 텐데 말이죠.

아...감사합니다

a,c,i,n,t는 모든 단어에 공통으로 들어가있어서 빼고 생각하면 될 줄 알았는데

백트래킹에서 걸러내지를 못하나보네요

31번째 줄과 32번째 줄을 보면

learned한 글자에 특정한 글자가 포함되지 않는 경우만 거르고 있습니다.

처음에 learned한 글자는 0이므로, 모든 글자를 안 배웠다고 처리한 건데요. 사실.. a/c/i/n/t는 이미 빼 놓은 글자이고...

set에도 항상 포함이 안 되는 것이니.. 넣을 필요도 없을 거에요.

그렇지 않는다면, 최악의 경우 26C13이 되어서 1040만 즈음이 나오겠지요. 35만과는 30배 차이가 납니다.