시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
8 초 1024 MB 45 27 26 61.905%

문제

민규와 명진이는 타자연습 대결을 하고 있다. 타자연습은 $N$개의 단어들로 이루어져 있으며, 각 단어는 알파벳 대문자 A부터 D까지로만 이루어져 있다. 단어의 첫 글자부터 시작해 현재 위치의 글자에 해당하는 정확한 글자를 입력하면 다음 글자로 넘어가며, 모든 글자를 입력했다면 엔터 키를 눌러 다음 단어로 넘어가는 방식이다. 이 프로그램은 오타에 관대하기 때문에, 잘못된 글자를 입력하면 패널티 없이 무시되기만 한다. 즉, 단어들을 수열로 보았을 때 타자연습에 주어진 단어가 입력한 글자들을 모은 단어의 부분 수열인 경우 단어를 입력하는 데에 성공하는 것이다.

민규는 실력이 부족해 명진이를 이길 수 없자, 꼼수를 쓰기로 했다. 프로그램이 허술해 붙여넣기가 가능한 것을 발견한 민규는 하나의 단어만을 만들어, 계속 붙여넣는 것으로 모든 단어들을 순식간에 통과하려고 한다. 즉, 민규의 단어는 단어들을 수열로 보았을 때 $N$개의 단어들을 모두 부분 수열로 가져야 한다. 이 때, 민규는 타자 속도가 느리므로 그 단어의 길이를 최소로 하고 싶다. 민규를 위해 사용할 단어를 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에 단어의 수 $N$이 주어진다. $(1 \leq N \leq 6)$

이후 $N$개의 줄에 걸쳐 타자연습 단어를 나타내는 문자열 $S_i$가 주어진다. $S_i$는 대문자 A, B, C, D로만 이루어져 있으며 길이는 $9$ 이하이다.

출력

첫 번째 줄에 사용할 문자열을 출력한다. 단, 가능한 문자열이 여럿 있을 경우 사전순으로 최소인 것을 출력해야 한다.

예제 입력 1

5
AACABBA
BACBA
DDDBBACB
CCCCBABD
DDDDDDD

예제 출력 1

AABCACCCDDDBBACBDDDD

예제 입력 2

6
AAAAAAAAA
BBBBBBBBB
CCCCCCCCC
DDDDDDDDD
ABABABABA
CDCDCDCDC

예제 출력 2

AAAAABABABABABBBBBCCCCCDCDCDCDCDDDDD

예제 입력 3

6
AAAAAAAAA
BBBBBBBBB
CCCCCCCCC
DDDDDDDDD
ACDBABBAC
CBDDDBBAA

예제 출력 3

AAAAAAABBBBCBCCCCCCCDDDBBABBACDDDDDD

출처

High School > 경기과학고등학교 > 나는코더다 2020 송년대회 D번