NVWLS
시간 제한6초메모리 제한1024 MB
단어 사전과 자음만 남은 메시지가 주어질 때, 모음과 공백을 제거하면 메시지가 되는 문장을 복원하되 모음의 총개수가 최대가 되도록 한다.
문제
NVWLS, 즉 "No Vowels" 퍼즐은 퍼즐 애호가들 사이에서 인기가 많다. 예를 들어 다음과 같은 모음 없는 메시지를 보자.
BTWNSBTLSHDNGNDTHBSNCFLGHTLSTHNNCFQLSN
이는 버지니아주 CIA 본부에 있는 유명한 "Kryptos" 조각상에 새겨져 있다. 이 메시지는 다음 문장에서 모든 모음과 공백을 제거해 얻는다.
BETWEEN SUBTLE SHADING AND THE ABSENCE OF LIGHT LIES THE NUANCE OF IQLUSION
사전(문장을 구성할 수 있는 단어의 집합)과 메시지(그 단어들만 사용한 문장에서 모든 모음과 공백을 제거한 것)가 주어질 때, 사전의 단어만으로 원래 문장을 복원하라!
입력
첫째 줄에는 사전에 있는 단어의 수를 나타내는 정수 n이 주어진다. 다음 n개 줄에는 각각 하나 이상의 대문자 영어 알파벳으로 이루어진 사전 단어가 주어진다. 각 단어에는 자음이 하나 이상 있다.
이 문제에서 문자 A, E, I, O, U는 모음이고 나머지 문자는 모두 자음이다.
사전 다음에는 모음 없는 메시지를 나타내는 대문자 자음 한 줄이 비어 있지 않게 주어진다. 모음 없는 메시지는 사전 단어만으로 적어도 한 가지 방법으로 구성할 수 있음이 보장된다.
사전 단어의 모든 문자 수의 합은 100 000 이하이다. 모음 없는 메시지의 문자 수는 300 000을 넘지 않는다.
출력
모든 공백과 모음을 제거하면 원래의 모음 없는 메시지가 되는 사전 단어의 나열을 공백으로 구분해 출력한다. 복원 방법이 여러 가지라면 모음의 총 개수가 가장 많은 것을 고른다. 그래도 여러 가지라면 아무 것이나 출력해도 된다. 어떤 입력에서도 프로그램이 15 000 000자를 넘게 출력할 필요는 없다.