알파벳 분수

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

요약

처음 N개 알파벳을 분자와 분모에 나눠 쓴 분수가 주어질 때, 같은 값을 갖도록 모든 글자를 한 번씩 쓴 완전 괄호 수식을 만든다.

난이도: 보통10점 중 7점
유형: 수학, 재귀, 백트래킹
정답자: 아직 제출이 없습니다

문제

알파벳 분수란 분자와 분모가 알파벳으로 이루어진 분수이다. 분자와 분모는 'A'부터 처음 N개의 문자로 이루어져 있어야 한다. 모든 알파벳은 단 한 번만 알파벳 분수에 포함되어 있어야 한며, 분자와 분모에는 하나 이상의 알파벳이 있어야 한다. 알파벳 분수는 '/'를 이용해 분자와 분모를 구분한다. 따라서, ABC/D, CAFE/BD는 알파벳 분수이고, CAF/ABDE, AB/CE, AB/D, B/, ABC는 아니다.

알파벳 확장은 알파벳 분수에 포함된 알파벳을 알파벳의 순서대로 나열하고, 인접한 글자 사이에 '/' 기호를 넣은 뒤, N-1개의 괄호쌍을 이용해 만들 수 있다. 알파벳 분수와 알파벳 확장은 동등한 수식이어야 한다. 예를 들어 CA/BD의 알파벳 확장으로 ((A/(B/C))/D가 될 수 있는 이유는 A, B, C, D가 얼마든 두 식의 값이 항상 같기 때문이다. 또 다른 예로 CAF/BED의 알파벳 확장은 (A/(B/((C/D)/(E/F))))이다.

알파벳 분수가 주어진다. 이 분수의 알파벳 확장을 구해보자.

입력

첫째 줄에 알파벳 분수가 주어진다.

출력

입력으로 주어진 알파벳 분수의 알파벳 확장을 출력한다. 여러가지가 있는 경우 아무거나 하나만 출력하고, 없는 경우에는 "None"을 출력한다.

제한

2 ≤ N ≤ 26

예제6

예제 1
입력
```
A/B
```
예상 출력
```
(A/B)
```
예제 2
입력
```
B/A
```
예상 출력
```
None
```
예제 3
입력
```
CA/BD
```
예상 출력
```
((A/(B/C))/D)
```
예제 4
입력
```
A/BC
```
예상 출력
```
((A/B)/C)
```
예제 5
입력
```
CAF/BED
```
예상 출력
```
(A/(B/((C/D)/(E/F))))
```

예제 6

입력

ACDE/BFGH

예상 출력

(A/(((B/C)/D)/(((E/F)/G)/H)))