Run Length Plus timer 1s memory - MB

기본적인 압축 방법 중에는 Run length 압축법이 있다. 이 경우 임의의 문자 X가 연달아 N번 반복이 될 경우 NX 형태로 표기하는 방법이다 한글자만 반복될 경우에는 단순히 해당 문자를 적는다. 예를 들어 "3ABBC10D"의 는 "AAABBCDDDDDDDDDD" 를 변환한 결과이다.

이 문제에서 다루게 될 Run length plus 압축법은 단순히 하나의 문자에 대해서만 압축을 하는 것이 아닌, 반복되는 부분 문자열에 대해서도 헤아리는 방법이다. 해당 문자열 S가 연달아 N번 반복이 될 경우( 예를 들어 "ABCABCABC"의 경우에서는 S = "ABC"가 연달아 반복되는 경우이며, 이 경우에는 N=3이다.)에는 N(S)의 형태로 표기를 하는 것이다. 괄호안에 괄호가 존재 하는 경우도 가능하며, 압축된 문자열자체도 문자열로 간주하여 압축할 수 있다. 예를 들어 "X2(2A3(BC))X"는 "XAABCBCBCAABCBCBCX"를 압축한 결과이다.

알파벳 대문자로 이뤄진 문자열이 주어질 때 압축되어 생성되는 문자열의 길이가 최소가 될 경우를 찾는 프로그램을 작성하라. 만약 이것이 여럿이 있을 경우 사전순으로 가장 빠른 것을 출력하라( 본 문제에서는 '(', ')', '0' 이상 '9' 이하의 숫자, 'A' 이상 'Z'이하의 대문자를 다루게 되는데, '(', ')', '0', '1', ..., '9', 'A', 'B', ... 'Z' 순이다 ).