Pieces of Parentheses 1초 128MB
문제
당신은 반에서 프로그램을 교육하고 있고, 균형잡힌 괄호 문자열에 대해 가르치기를 원한다. 당신은 완벽한 시각 자료인, 매우 길고 균형 잡힌 괄호 문자열을 수업 자료로 가져왔다. 하지만, 아쉽게도, 무슨 이유에서인지, 당신의 시각 자료는 조각들로 부서졌고, 심지어 몇 조각은 없어졌다. 당신은 최선을 다해 괄호를 복원하길 원했다. 괄호 문자열이 적혀 있는 조각 목록이 주어졌을 때, 어떻게 해야 이 조각들을 이어 붙여 가장 긴 균형잡힌 괄호 문자열을 만들 수 있을 까? 각 조각은 한 번만 사용되어야 하며, 조각은 뒤집을 수 없다.
균형잡힌 괄호 문자열은 다음과 같이 정의된다.
빈 문자열은 균형잡힌 괄호 문자열이다.
A와 B가 균형잡힌 괄호 문자열이면, AB도 균형잡힌 괄호 문자열이다.
A가 균형잡힌 괄호 문자열이면, (A)도 균형잡힌 괄호 문자열이다.
입력
첫 번째 줄에 조각의 갯수 n이 주어진다. (1 ≤ n ≤ 300)
두 번째 줄부터 n개의 줄에, 각 조각에 쓰여있는 괄호문자열 s가 주어진다. (1 ≤ |s| ≤ 300)
출력
첫 번째 줄에, 만들 수 있는 가장 긴 균형잡힌 괄호문자열의 길이를 출력한다.
예제 #1
3
())
((()
)()
10
예제 #2
5
)))))
)
((
))((
(
2
로그인해야 코드를 작성할 수 있어요.