Informatica Online Judge

  괄호 매칭 2 [1564 / 061C]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 28   Total Tried : 37


The Champion of this Problem (C++) : gs18012 - 0ms / 364byte
My Best Submission (C++) : N/A

[JKJeong 2016]

Background

경곽이는 컴퓨터 프로그래밍 시간에 괄호매칭에 대해서 배웠다.

배운 내용을 복습하기 위해서 다음과 같은 문제를 생각했다.

"(", ")"로만 이루어진 길이가 n인 문자열에서

임의의 i번째 문자로부터 j번째 문자까지 올바른 괄호열은 몇개나 존재하는지 구해보자.
(단, 1 <= i <= j <= n)

이 문제를 생각한 경곽이는 어떻게 해결해야할지 고민하고 있다.

고민하는 경곽이를 도와 문제를 해결해보자.

Input

첫 번째 줄에 "(", ")"의 두 문자로만 이루어진 문자열 이 주어진다.

[입력값의 정의역]
2 <= 문자열의 길이 <= 7,777

Output

첫 번째 줄에는 가능한 괄호열의 수를 출력한다.

IO Example

입력
)()(())

출력
4

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]