레이팅 미적용설명
소 베시(Bessie)는 새 노트북에 균형 잡힌 괄호 문자열을 입력하려고 하지만, (큰 발굽 때문에) 꽤 서툴러서 자꾸 문자를 잘못 입력한다. 문자열이 균형 잡히게 만들기 위해 반대로 바꿔야 하는(즉, 왼쪽 괄호를 오른쪽 괄호로, 또는 그 반대로) 문자의 최소 개수를 계산하여 베시를 도와주자.
괄호 문자열이 "균형 잡혔다"는 것은 (의 개수와 )의 개수가 같고, 문자열의 어떤 접두사에서도 (의 개수가 )의 개수 이상인 것을 말한다.
제약
입력 형식
첫째 줄: 길이가 짝수이고 최대 100,000자인 괄호 문자열.
출력 형식
문자열을 균형 잡힌 문자열로 바꾸기 위해 뒤집어야 하는 괄호의 최소 개수를 나타내는 정수 하나.
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:
입력을 읽을 파일
clumsy.in · 출력을 쓸 파일 clumsy.out예제 1
입력
())(출력
2설명
Output details: The last parenthesis must be toggled, and so must one of the two middle right parentheses.
문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > November > Silver
태그