시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 680 | 399 | 347 | 61.964% |
천방지축 베시(소, 1세)는 외양간을 탈출해서 풀로 뒤덮인 산등성이에 숨었다. 농부인 존씨는 베시를 다시 잡기위해 온 풀숲을 샅샅히 뒤졌지만 찾지 못하였다. 안타깝게도 그는 베시를 찾는데 어려워하고 있다. 존에게 그 풀밭은 N개의 소괄호로 이루어진 문자열처럼 보였기 때문이다. 예를 들면, 아래와 같다.
)((()())())
존은 베시의 뒷다리가 왼쪽 소괄호 두 개가 붙어있는 것 (( 과 똑같이 생긴 것을 알고있다. 또한 베시의 앞다리는 오른쪽 소괄호 두 개가 붙어있는 것 )) 과 똑같이 생겼다. 베시의 위치는 뒷다리의 위치가 x이고 앞다리의 위치가 y라고 할때 x < y가 되는 쌍으로 표현될 수 있다.
이때, 베시가 서있는 위치가 될 수 있는 서로 다른 순서쌍들의 개수를 구하여 존을 도와보자.
첫 째줄에 N개의 소괄호로 이루어진 문자열이 주어진다. (1 ≤ N ≤ 50,000)
첫 째줄에 베시가 서있을 수 있는 위치의 개수를 출력한다. (즉, 가 나타나는 곳의 인덱스 x와 가 나타나는 곳의 인덱스 y에서 x<y가 되는 서로 다른 순서쌍들의 개수를 출력한다.)
)((()())())
4
예제에서 베시가 있을 수 있는 곳은 아래의 네가지이다.
Olympiad > USA Computing Olympiad > 2012-2013 Season > USACO November 2012 Contest > Bronze 1번