중첩 반복 압축

시간 제한2초메모리 제한1024 MB

요약

소문자 문자열(최대 200자)을 입력받아, 숫자와 괄호로 반복을 묶는 표현 중 가장 짧은 것을 출력합니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 문자열 매칭, 문자열
정답자: 아직 제출이 없습니다

문제

이메일로 보낼 소문자 문자열이 여러 개 있는데, 그중 일부는 너무 길어서 그대로 입력하기가 번거롭다. 반복되는 부분이 보여서 간단한 압축 방법을 써 보기로 했다. 반복되는 부분을 괄호로 묶고, 앞에 반복 횟수를 숫자로 붙이는 방식이다. 예를 들어 문자열 "abababaaaaa"는 "3(ab)5(a)" 또는 "a3(ba)4(a)"로 나타낼 수 있다. 압축 표현의 문법은 시작 기호 $S$ 에 대한 BNF로 다음과 같다.

<S> ::= <R> | <R> <S>
<R> ::= <L> | <D> `(`<S>`)`
<D> ::= `2` | `3` | `4` | `5` | `6` | `7` | `8` | `9`
<L> ::= `a` | `b` | `c` | `d` | `e` | `f` | `g` | `h` | `i` | `j` | `k` | `l` | `m` | `n` | `o` | `p` | `q` | `r` | `s` | `t` | `u` | `v` | `w` | `x` | `y` | `z`

반복 횟수는 한 자리 숫자로만 적을 수 있어 최대 9이다. 대신 중첩하면 더 많이 반복할 수 있다. a가 30개 이어진 문자열은 "6(5(a))" 또는 "3(5(2(a)))"로 나타낼 수 있다.

주어진 문자열을 이 방식으로 나타내는 가장 짧은 표현을 구하라.

입력

한 줄에 소문자로만 이루어진 문자열이 주어진다. 문자열의 길이는 1 이상 200 이하이다.

출력

입력된 문자열을 나타내는 가장 짧은 표현을 한 줄에 출력한다. 가장 짧은 표현이 두 개 이상이면 그중 어느 것을 출력해도 된다.

예제3

예제 1
입력
```
abababaaaaa
```
예상 출력
```
3(ab)5(a)
```
예제 2
입력
```
abababcaaaaaabababcaaaaa
```
예상 출력
```
2(3(ab)c5(a))
```
예제 3
입력
```
abcdefg
```
예상 출력
```
abcdefg
```