시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
8 초 | 1024 MB | 78 | 49 | 46 | 63.889% |
민규와 명진이는 타자연습 대결을 하고 있다. 타자연습은 $N$개의 단어들로 이루어져 있으며, 각 단어는 알파벳 대문자 A
부터 D
까지로만 이루어져 있다. 단어의 첫 글자부터 시작해 현재 위치의 글자에 해당하는 정확한 글자를 입력하면 다음 글자로 넘어가며, 모든 글자를 입력했다면 엔터 키를 눌러 다음 단어로 넘어가는 방식이다. 이 프로그램은 오타에 관대하기 때문에, 잘못된 글자를 입력하면 패널티 없이 무시되기만 한다. 즉, 단어들을 수열로 보았을 때 타자연습에 주어진 단어가 입력한 글자들을 모은 단어의 부분 수열인 경우 단어를 입력하는 데에 성공하는 것이다.
민규는 실력이 부족해 명진이를 이길 수 없자, 꼼수를 쓰기로 했다. 프로그램이 허술해 붙여넣기가 가능한 것을 발견한 민규는 하나의 단어만을 만들어, 계속 붙여넣는 것으로 모든 단어들을 순식간에 통과하려고 한다. 즉, 민규의 단어는 단어들을 수열로 보았을 때 $N$개의 단어들을 모두 부분 수열로 가져야 한다. 이 때, 민규는 타자 속도가 느리므로 그 단어의 길이를 최소로 하고 싶다. 민규를 위해 사용할 단어를 구하는 프로그램을 작성하여라.
첫 번째 줄에 단어의 수 $N$이 주어진다. $(1 \leq N \leq 6)$
이후 $N$개의 줄에 걸쳐 타자연습 단어를 나타내는 문자열 $S_i$가 주어진다. $S_i$는 대문자 A, B, C, D
로만 이루어져 있으며 길이는 $9$ 이하이다.
첫 번째 줄에 사용할 문자열을 출력한다. 단, 가능한 문자열이 여럿 있을 경우 사전순으로 최소인 것을 출력해야 한다.
5 AACABBA BACBA DDDBBACB CCCCBABD DDDDDDD
AABCACCCDDDBBACBDDDD
6 AAAAAAAAA BBBBBBBBB CCCCCCCCC DDDDDDDDD ABABABABA CDCDCDCDC
AAAAABABABABABBBBBCCCCCDCDCDCDCDDDDD
6 AAAAAAAAA BBBBBBBBB CCCCCCCCC DDDDDDDDD ACDBABBAC CBDDDBBAA
AAAAAAABBBBCBCCCCCCCDDDBBABBACDDDDDD
High School > 경기과학고등학교 > 나는코더다 2020 송년대회 D번