BOJ 5872 Clumsy Cows
BOJ 5872 Clumsy Cows
문제 내용
여는 괄호 (와 닫는 괄호)로 이루어진 문자열이 주어집니다. 이 문자열을 올바른 괄호 문자열로 만들기 위해 바꿔야 하는 글자의 최소 개수를 출력하세요.
입력
첫 줄에 문자열이 주어집니다. 이 문자열의 길이는 이하이며, 짝수입니다.
출력
문제의 정답을 출력합니다.
문제 풀이
스포일러
이 문제는 잘 알려진 그리디로 풀 수 있습니다.
(를 +1, )를 -1로 두면 누적 합이 음수가 되는 시점의 )를 (로 바꿔주고, 최종 합이 양수라면 그것의 절반만큼의 마지막 (를 )로 바꿔주면 됩니다.Last updated on