레트로

시간 제한0.5초메모리 제한512 MB

요약

화면의 물체가 한 칸씩 아래로 내려오는 동안 주인공이 좌우로 움직이며 괄호를 주워, 만들 수 있는 가장 긴 올바른 괄호 문자열과 그 길이를 구한다. 그 길이의 답이 여러 개면 사전순으로 가장 앞선 것을 출력한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 그리디, 문자열, 구현
정답자: 아직 제출이 없습니다

문제

미르코가 크리스마스 선물로 비디오 게임기를 받았다. 플레이스테이션 4나 엑스박스 원이 아니라 아타리 2600이었고, 게임 하나가 딸려 왔다. 게임의 주인공은 화면 맨 아래에 서 있고, 화면의 나머지 부분에는 여러 물체가 흩어져 아래로 떨어진다.

화면은 $R$ 개의 행과 $S$ 개의 열로 이루어진 $R \times S$ 픽셀 격자다. 주인공은 맨 아랫줄의 픽셀 한 칸을 차지하며 M으로 표시한다. 나머지 픽셀은 .(빈 칸), *(폭탄), ((여는 괄호), )(닫는 괄호) 중 하나로 표시한다.

한 번의 이동에서 주인공은 왼쪽이나 오른쪽으로 한 픽셀 움직일 수 있고, 움직이지 않아도 된다. 같은 시각에 나머지 물체는 모두 아래로 한 픽셀 내려가며, 화면 밖으로 나가기도 한다. 주인공이 괄호와 같은 위치에 놓이면 그 괄호를 주웠다고 하고, 지금까지 모은 괄호 배열의 끝에 그 괄호를 덧붙인다. 주인공의 목표는 가능한 한 긴 올바른 괄호 수식을 모으는 것이다.

올바른 괄호 수식은 다음과 같이 귀납적으로 정의한다.

()는 올바른 수식이다.
$a$ 가 올바른 수식이면 $(a)$ 도 올바른 수식이다.
$a$ 와 $b$ 가 올바른 수식이면 $ab$ 도 올바른 수식이다.

주인공이 폭탄과 같은 위치에 놓이거나 모든 물체가 화면 밖으로 떨어지면 게임이 끝난다.

입력

첫째 줄에 화면의 크기를 나타내는 양의 정수 $R$ , $S$ 가 주어진다. ( $1 \le R, S \le 300$ )

다음 $R$ 개 줄에는 화면의 처음 상태를 나타내는 문자가 한 줄에 $S$ 개씩 주어진다. 각 문자는 M, ., *, (, ) 중 하나다.

입력 자료에서 주인공이 모을 수 있는 올바른 괄호 수식은 항상 하나 이상 존재한다.

출력

첫째 줄에 미르코가 모을 수 있는 가장 긴 올바른 괄호 수식의 길이를 출력한다.

둘째 줄에 그 수식을 출력한다. 길이가 가장 긴 올바른 괄호 수식이 여러 개이면 사전순으로 가장 앞서는 것을 출력한다.

힌트

첫 번째 예제에서 주인공의 이동은 왼쪽, 왼쪽, 오른쪽, 오른쪽이다.

두 번째 예제에서 주인공의 이동은 제자리, 제자리, 제자리, 오른쪽, 왼쪽이다.

세 번째 예제에서 주인공의 이동은 제자리, 제자리, 오른쪽이다.

예제3

예제 1
입력
```
5 4
..).
.)(.
(.)*
*(.*
..M.
```
예상 출력
```
4
(())
```
예제 2
입력
```
6 3
)(.
*..
(**
)()
().
M..
```
예상 출력
```
4
()()
```
예제 3
입력
```
6 3
((.
*..
(**
)()
().
M..
```
예상 출력
```
2
()
```