cinador   3년 전

문제

길이가 긴 영단어는 영단어의 앞과 뒤 각각 한 문자만 남기고 나머지 중간 문자열은 중간 문자열의 길이에 해당하는 정수로 바꾸는 방법으로 생략할 수 있다. 예를 들어, "internationalization" 은 "i18n",           "localization" 은 "l10n", "accessibility" 은 "a11y" 으로 생략할 수 있다.

이 문제에서는 위의 생략 방법을 일반화해서, 문자열의 앞과 뒤 각각 한 문자 이상을 남기고 나머지 중간 문자열을 중간 문자열의 길이에 해당하는 정수로 바꾼 문자열을 원래 문자열의 "생략 문자열"이라고 하자. 예를 들어, "i18n", "int13tion", "i1ternationalization" 은 "internationalization" 의 생략 문자열이지만, "i123n", "i4national3tion", "19n" 은 "internationalization" 의 생략 문자열이 아니다. 또한, 어떤 문자열도 생략하지 않은 "internationalization" 도 "internationalization" 의 생략 문자열에 포함된다고 하자.

당신은 알파벳 소문자로 이루어진 단어가 N개 포함되어 있는 사전을 갖고 있고, 이 사전에 실린 단어를 그 단어의 생략 문자열 중 하나로 변환하여 새로운 사전을 만들려고 한다. 이 때, 단어가 다르더라도 변환할 수 있는 생략 문자열이 같은 경우가 있는데, 이런 생략 문자열은 생략 문자열만 보고 처음 사전에 포함되어 있는 단어로 복원할 수 없기 때문에 새로운 사전에 포함될 수 없다. 예를 들어, 처음 사전에 "love" 와 "live" 가 있었다고 하면, 두 단어 모두 "l2e" 로 변환할 수 있기 때문에, "l2e" 만 보고 원래 단어가 "love" 인지 "live" 인지 알 수 없으므로 "l2e" 는 새로운 사전에 포함될 수 없다. 이 경우, "love" 를 "lo1e" 로, "live" 를 "li1e" 로 변환한다면 두 생략 문자열 각각을 보고 원래 단어로 복원할 수 있다.

알파벳 소문자로 이루어진 단어가 N개 포함되어 있는 사전으로 새로운 사전을 만들 때, 만들 수 있는 새로운 사전 중에서, 각 단어를 생략 문자열로 변환하는 데에 쓰인 정수 N개의 합의 최댓값을 구하여라. 이 때, 어떤 문자열도 생략하지 않고 원래 단어가 그대로 새로운 사전에 포함된 경우, 생략 문자열로 변환하는 데에 쓰인 정수는 0이다.

ㅤ

입력

입력은 최대 50개의 테스트 케이스로 이루어져 있으며, 각 테스트 케이스는 다음과 같은 형식을 갖는다.

N

s1

s2

...

sN

첫 줄에는 사전에 포함되어 있는 단어의 개수 N (1 ≤ N ≤1,000) 이 주어진다. 다음 N줄에는, 생략 문자열로 변환하려고 하는 단어가 한 줄에 하나씩 주어진다. 각 단어의 길이는 3이상 30이하이며, 알파벳 소문자로만 이루어져 있다. 사전에 포함되어 있는 단어는 모두 다르다.

입력의 마지막에는 0 하나가 주어진다. 

ㅤ

출력

각 테스트 케이스에 대해, 원래 단어로 복원할 수 있게끔 각 단어를 생략 문자열로 변환하여 새로운 사전을 만들었을 때, 생략 문자열로의 변환에 쓰인 정수들의 합의 최댓값을 한 줄에 하나씩 출력한다.

댓글을 작성하려면 로그인해야 합니다.