레이팅 미적용설명
소 베시(Bessie)가 탈출하여 키 큰 풀로 덮인 언덕에 숨어 있다. 베시를 다시 붙잡으려는 농부 존(Farmer John)은 들키지 않고 접근하기 위해 손과 무릎으로 풀숲을 기어가기로 했다. 안타깝게도 이 시점에서는 베시를 발견하기가 어렵다. 농부 존 앞의 풀숲은 N개 (1 <= N <= 50,000)의 괄호로 이루어진 문자열처럼 보인다. 예를 들면 다음과 같다.
)((()())())
농부 존은 베시의 뒷다리가 인접한 왼쪽 괄호 쌍 ((와 똑같이 생겼고, 앞다리는 인접한 오른쪽 괄호 쌍 ))와 똑같이 생겼다는 것을 알고 있다. 따라서 베시의 위치는 위치 x에 ((가 있고 위치 y에 ))가 있는 인덱스 쌍 x < y로 표현할 수 있다. 베시가 서 있을 수 있는 서로 다른 위치의 수를 계산하시오.
제약
입력 형식
첫째 줄: 길이 N (1 <= N <= 50,000)의 괄호 문자열.
출력 형식
베시가 서 있을 수 있는 위치의 수, 즉 인덱스 x에 패턴 ((가 있고 인덱스 y에 패턴 ))가 있는 서로 다른 인덱스 쌍 x < y의 개수.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
cowfind.in · 출력을 쓸 파일 cowfind.out예제 1
입력
)((()())())출력
4문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > November > Bronze
태그