시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 468 124 92 29.582%

문제

백승환와 이석원은 한 팀이 되어 English 끝말대회에 출전했다. 앞단어의 마지막 글자가 뒷단어의 처음 글자와 같도록 단어를 차례대로 늘어놓는 게임 말이다. 단어는 주어지는 사전에 나와 있는 단어만 사용해야 하며 (영혼이 맑아질 만한 사실을 한 가지 가르쳐 주자면) 사전의 단어들은 모두 모음(A, E, I, O, U)으로만 이루어져있다는 것이다. 단어의 시작은 어떤 단어이든지 상관이 없고 같은 단어가 두 번 이상 사용되면 안 되며 게임에 사용된 단어의 길이의 합이 그 팀의 점수가 된다.

점수가 최대가 되도록 끝말잇기 규칙에 맞게 단어를 늘어놓는 프로그램을 만들어 승환이와 석원이를 도와주도록 하자.

입력

첫 줄에 사전에 포함된 단어 개수 N이 입력된다. (N ≤ 16)

두 번째 줄부터 N+1번째 줄까지 사전에 포함된 단어들이 한 줄에 하나씩 입력된다. 단어는 대문자 A, E, I, O, U로만 이루어져 있고 하나의 단어는 그 길이가 100을 넘지 않는다. 같은 단어가 두 번 주어지지 않는다.

출력

한 줄에 단어를 잘 늘어 놨을 때 얻을 수 있는 최대 점수를 출력한다.

예제 입력 1

3
AEIOU
UIU
EO

예제 출력 1

8
W3sicHJvYmxlbV9pZCI6IjIzMjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwNWRcdWI5ZDBcdWM3ODdcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmMzMVx1YzJiOVx1ZDY1OFx1YzY0MCBcdWM3NzRcdWMxMWRcdWM2ZDBcdWM3NDAgXHVkNTVjIFx1ZDMwMFx1Yzc3NCBcdWI0MThcdWM1YjQgRW5nbGlzaCBcdWIwNWRcdWI5ZDBcdWIzMDBcdWQ2OGNcdWM1ZDAgXHVjZDljXHVjODA0XHVkNTg4XHViMmU0LiBcdWM1NWVcdWIyZThcdWM1YjRcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWI0YjdcdWIyZThcdWM1YjRcdWM3NTggXHVjYzk4XHVjNzRjIFx1YWUwMFx1Yzc5MFx1YzY0MCBcdWFjMTlcdWIzYzRcdWI4NWQgXHViMmU4XHVjNWI0XHViOTdjIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWIyOThcdWM1YjRcdWIxOTNcdWIyOTQgXHVhYzhjXHVjNzg0IFx1YjlkMFx1Yzc3NFx1YjJlNC4gXHViMmU4XHVjNWI0XHViMjk0IFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWMwYWNcdWM4MDRcdWM1ZDAgXHViMDk4XHVjNjQwIFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM1YjRcdWI5Y2MgXHVjMGFjXHVjNmE5XHVkNTc0XHVjNTdjIFx1ZDU1OFx1YmE3MCAoXHVjNjAxXHVkNjNjXHVjNzc0IFx1YjlkMVx1YzU0NFx1YzljOCBcdWI5Y2NcdWQ1NWMgXHVjMGFjXHVjMmU0XHVjNzQ0IFx1ZDU1YyBcdWFjMDBcdWM5YzAgXHVhYzAwXHViOTc0XHVjY2QwIFx1YzhmY1x1Yzc5MFx1YmE3NCkgXHVjMGFjXHVjODA0XHVjNzU4IFx1YjJlOFx1YzViNFx1YjRlNFx1Yzc0MCBcdWJhYThcdWI0NTAgXHViYWE4XHVjNzRjKEEsIEUsIEksIE8sIFUpXHVjNzNjXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjJlOFx1YzViNFx1Yzc1OCBcdWMyZGNcdWM3OTFcdWM3NDAgXHVjNWI0XHViNWE0IFx1YjJlOFx1YzViNFx1Yzc3NFx1YjRlMFx1YzljMCBcdWMwYzFcdWFkMDBcdWM3NzQgXHVjNWM2XHVhY2UwIFx1YWMxOVx1Yzc0MCBcdWIyZThcdWM1YjRcdWFjMDAgXHViNDUwIFx1YmM4OCBcdWM3NzRcdWMwYzEgXHVjMGFjXHVjNmE5XHViNDE4XHViYTc0Jm5ic3A7XHVjNTQ4IFx1YjQxOFx1YmE3MCBcdWFjOGNcdWM3ODRcdWM1ZDAgXHVjMGFjXHVjNmE5XHViNDFjIFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NTggXHVkNTY5XHVjNzc0IFx1YWRmOCBcdWQzMDBcdWM3NTggXHVjODEwXHVjMjE4XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODEwXHVjMjE4XHVhYzAwIFx1Y2Q1Y1x1YjMwMFx1YWMwMCBcdWI0MThcdWIzYzRcdWI4NWQgXHViMDVkXHViOWQwXHVjNzg3XHVhZTMwIFx1YWRkY1x1Y2U1OVx1YzVkMCBcdWI5ZGVcdWFjOGMgXHViMmU4XHVjNWI0XHViOTdjIFx1YjI5OFx1YzViNFx1YjE5M1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHViOWNjXHViNGU0XHVjNWI0IFx1YzJiOVx1ZDY1OFx1Yzc3NFx1YzY0MCBcdWMxMWRcdWM2ZDBcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwXHVjOGZjXHViM2M0XHViODVkIFx1ZDU1OFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVjMGFjXHVjODA0XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxYyBcdWIyZThcdWM1YjQgXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LiAoTiAmbGU7IDE2KTxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVhZTRjXHVjOWMwIFx1YzBhY1x1YzgwNFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MWMgXHViMmU4XHVjNWI0XHViNGU0XHVjNzc0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4gXHViMmU4XHVjNWI0XHViMjk0IFx1YjMwMFx1YmIzOFx1Yzc5MCBBLCBFLCBJLCBPLCBVXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAgXHVkNTU4XHViMDk4XHVjNzU4IFx1YjJlOFx1YzViNFx1YjI5NCBcdWFkZjggXHVhZTM4XHVjNzc0XHVhYzAwIDEwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWFjMTlcdWM3NDAgXHViMmU4XHVjNWI0XHVhYzAwIFx1YjQ1MCBcdWJjODggXHVjOGZjXHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWQ1NWMgXHVjOTA0XHVjNWQwIFx1YjJlOFx1YzViNFx1Yjk3YyBcdWM3OTggXHViMjk4XHVjNWI0IFx1YjFhOFx1Yzc0NCBcdWI1NGMgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjMyMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IldPUkRTIiwiZGVzY3JpcHRpb24iOiI8cD5JbyBhbmQgQW8gYXJlIHBsYXlpbmcgYSB3b3JkIGdhbWUuIFRoZXkgYWx0ZXJuYXRlbHkgc2F5IHdvcmRzIGNvbnNpc3Rpbmcgb2Ygdm93ZWxzIG9ubHkgc28gdGhhdCB0aGUgZmlyc3QgbGV0dGVyIG9mIGV2ZXJ5IG5ldyB3b3JkIGlzIHRoZSBzYW1lIGFzIHRoZSBsYXN0IGxldHRlciBvZiB0aGUgcHJldmlvdXMgd29yZC4gQSBnYW1lIGNhbiBzdGFydCB3aXRoIGFueSB3b3JkLjxcL3A+XHJcblxyXG48cD5JdCBpcyBmb3JiaWRkZW4gdG8gc2F5IGFueSB3b3JkIHR3aWNlLiBPbmx5IHdvcmRzIGZyb20gZ2l2ZW4gZGljdGlvbmFyeSBjYW4gYmUgdXNlZCBpbiBhIGdhbWUuPFwvcD5cclxuXHJcbjxwPkEgY29tcGxleGl0eSBvZiBhIGdhbWUgaXMgZGVmaW5lZCBhcyBhIHN1bSBvZiBsZW5ndGhzIG9mIGFsbCB0aGUgc3Bva2VuIHdvcmRzIGR1cmluZyB0aGUgZ2FtZS48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBkZXRlcm1pbmUgdGhlIG1heGltYWwgcG9zc2libGUgY29tcGxleGl0eSBvZiBhIGdhbWUgdGhhdCBjYW4gYmUgcGxheWVkIHVzaW5nIHdvcmRzIGZyb20gYSBnaXZlbiBkaWN0aW9uYXJ5LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgZmlsZSBjb250YWlucyBhIG5hdHVyYWwgbnVtYmVyIE4sIDEgJmxlOyBOICZsZTsgMTYsIHRoZSBudW1iZXJzIG9mIHdvcmRzIGluIGEgZGljdGlvbmFyeS4gRWFjaCBvZiBuZXh0IE4gbGluZXMgY29udGFpbnMgb25lIHdvcmQgZnJvbSBhIGRpY3Rpb25hcnkuIEEgd29yZCBpcyBhIHNlcXVlbmNlIG9mIGNoYXJhY3RlcnMgJmxzcXVvO0EmcnNxdW87LCAmbHNxdW87RSZyc3F1bzssICZsc3F1bztJJnJzcXVvOywgJmxzcXVvO08mcnNxdW87IGFuZCAmbHNxdW87VSZyc3F1bzsuIExlbmd0aCBvZiBldmVyeSB3b3JkIHdpbGwgYmUgMTAwIG9yIGxlc3MuIEFsbCB0aGUgd29yZHMgd2lsbCBiZSBkaWZmZXJlbnQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IGZpbGUgc2hvdWxkIGNvbnRhaW4gdGhlIG1heGltYWwgcG9zc2libGUgY29tcGxleGl0eSBvZiB0aGUgZ2FtZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2001 > Croatian Olympiad in Informatics 2번

  • 문제의 오타를 찾은 사람: chogahui05
  • 빠진 조건을 찾은 사람: jh05013