레이팅 미적용농부 존(Farmer John)의 소들은 모두 독특한 외모로 유명한 아주 특이한 품종이다. 각 소의 가죽에는 괄호 모양의 거대한 반점이 있다 (소가 향한 방향에 따라 왼쪽 괄호처럼 보이기도 하고 오른쪽 괄호처럼 보이기도 한다).
어느 날 아침, 농부 존은 소들을 각각 N마리씩 K줄로 세웠다 (1 <= K <= 10, 1 <= N <= 50,000). 소들이 제각기 임의의 방향을 향하고 있으므로, 이 배치는 K개의 길이 N인 괄호 문자열 S_1,..., S_k로 표현할 수 있다. 농부 존은 소들의 어떤 구간들이 "동시에 균형 잡혀" 있다는 것을 발견하고 크게 흥분했다. 소들의 구간 i...j가 동시에 균형 잡혔다는 것은 문자열 S_1,..., S_k 각각이 그 구간에서 균형 잡힌 경우뿐이다.
K개의 길이 N인 괄호 문자열이 주어질 때, 구간 i...j가 동시에 균형 잡히는 쌍 (i,j)의 개수를 세는 것을 농부 존에게 도와주자. 괄호 문자열이 균형 잡혔다는 것은 (의 개수와 )의 개수가 같고 모든 접두사에서 (의 개수가 )의 개수 이상인 것을 말한다.
첫째 줄: 두 정수 K와 N.
둘째 줄부터 K+1번째 줄까지: 각 줄에 길이 N의 괄호 문자열이 주어진다.
동시에 균형 잡힌 구간의 개수를 나타내는 정수 하나.
cbs.in · 출력을 쓸 파일 cbs.out3 14
)()((())))(())
()(()()()((())
)))(()()))(())3riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > November > Gold