input

4 10
antahrtica
antaxyztica
antaxyktica
antaxyutica

output

2

correct output 

3

위 코드를 살펴보면 이 문제를 단어 중 배워야 하는 글자의 수가 작은 단어를 먼저 배우는 로직으로 문제를 푸시는 것으로 보입니다. 하지만 이와 같은 탐욕적인 풀이로는 위와 같은 반례가 생길 수 있습니다.

반례에서 배워야하는 글자의 수가 작은 "antahrtica"를 먼저 배우게 된다면, 두번째줄의 "antaxyztica"를 배운 후에(이는 "antaxyktica", "antaxyutica" 를 고르더라도 마찬가지 입니다.)는 이미 습득한 글자의 수가 10개가 되어 버리므로 2개의 단어를 배운 이후에는 더 이상 단어를 배울 수 없게 됩니다. 하지만 "antaxyztica"를 먼저 배우게 된다면 3, 4번째 단어를 배우는 것이 가능하므로 총 3개의 단어를 배울 수 있어 가장 많은 단어를 배울 수 있는 경우가 됩니다. 

그러므로, 위 코드와 같은 탐욕적인 방식으로는 이 문제를 푸는 것은 불가능 합니다. 다른 로직을 생각해 보셨으면 좋겠습니다.

답변 감사합니다. 다른 접근 방법을 써야 하나 보네요. 다시 생각해 보겠습니다.