괄호 조각

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

요약

여러 개의 괄호 조각이 주어질 때, 일부를 골라 순서를 정해 이어 붙여 가장 긴 올바른 괄호 문자열을 만든다.

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

문제

프로그래밍 수업에서 올바른 괄호 문자열을 가르치려고 한다. 아주 긴 올바른 괄호 문자열이 적힌 멋진 교구 팻말도 준비했다. 그런데 어쩌다 보니 팻말이 여러 조각으로 부서졌고, 일부 조각은 사라졌을지도 모른다! 최선을 다해 다시 맞춰 보아야 한다. 각 조각에 적힌 괄호 문자열이 주어질 때, 조각 몇 개를 골라 원하는 순서로 이어 붙여서 만들 수 있는 가장 긴 올바른 괄호 문자열은 무엇일까? 각 조각은 최대 한 번만 사용할 수 있고, 조각을 뒤집을 수는 없다.

올바른 괄호 문자열은 다음과 같이 정의한다.

빈 문자열
$A$ 와 $B$ 가 모두 올바른 괄호 문자열일 때 $AB$
$A$ 가 올바른 괄호 문자열일 때 ( $A$ )

입력

첫째 줄에 조각의 개수 $n$ ( $1 \le n \le 300$ )이 주어진다.

다음 $n$ 개의 줄에는 각각 문자열 $s$ ( $1 \le |s| \le 300$ )가 하나씩 주어진다. $s$ 는 문자 (와 )로만 이루어져 있으며, 조각 하나를 나타낸다.

출력

조각들로 만들 수 있는 가장 긴 올바른 괄호 문자열의 길이를 정수 하나로 출력한다. 빈 문자열도 엄밀히 말하면 올바른 괄호 문자열이므로, 항상 길이가 0 이상인 문자열을 만들 수 있다 (빈 문자열은 교구로서 별 쓸모가 없겠지만).

예제2

예제 1
입력
```
3
())
((()
)()
```
예상 출력
```
10
```
예제 2
입력
```
5
)))))
)
((
))((
(
```
예상 출력
```
2
```