[중등부] 2025 KOI 2차대회 대비 모의고사 (2회차)

'('와 ')'만으로 이루어진 문자열을 괄호 문자열이라 한다. 그 중에서도 올바른 괄호 문자열은 다음과 같이 정의된다.

1. 빈 문자열은 올바른 괄호 문자열이다.

2. 문자열 S가 올바른 괄호 문자열일 때, S를 (와 )로 감싼 문자열 (S)도 올바른 괄호 문자열이다.

3. 문자열 S와 T가 올바른 괄호 문자열일 때, 이 두 문자열을 이어붙인 문자열 S+T도 올바른 괄호 문자열이다.

올바른 괄호 문자열의 예시로는 ()()(), (()), ()(())()()이 있다.

문자열 S의 접두사는 S의 첫번째 원소를 포함하는 S의 부분 문자열을 의미한다. abcd의 접두사로는 a, ab, abc, abcd가 있다. 빈 문자열은 접두사가 될 수 없음에 유의하라.

두 괄호 문자열 A, B에 대해, A의 길이 i\,(1\leq i\leq |A|)의 접두사를 a_i, B의 길이 j\,(1\leq j\leq |B|)의 접두사를 b_j라 할 때 a_i와 b_j를 이어붙인 문자열 a_i+b_j가 올바른 괄호 문자열인 순서쌍 (i,j)의 개수를 구하는 프로그램을 작성하시오.