题解

题目描述

给定一个长度为 $N$ 的只包含左括号 '(' 和右括号 ')' 的字符串，多多君每次可以顺序读取如下两种内容之一：

1. 一个单独的字符（'(' 或 ')'），算作 1 次处理。
2. 一个“有效括号子串”，算作 1 次处理。
   • 有效括号子串需满足：
     • 括号成对闭合；

题目内容

多多君在处理一个由左括号(和右括号)组成的字符串，多多君每次处理时可以顺序读取一个字符或者一个有效括号子串，求问多多君的最小处理次数

输入描述

第一行输入为一个整数 $N$ ,表示字符串的总长度 $(1<= N<=10,000)$

第二行输入为一个长度为 $N$ 字符串，字符串由 $($ 和 $)$ 组成

输出描述

输出为一个整数，表示字符串的最小处理次数

补充说明

有效括号子串需要满足：

1.括号成对闭合：每个 $'('$ 都有一个对应的 $')'$

2.正确嵌套顺序：右括号不能出现在对应的左括号之前

例如：$“()”、“()()”、“(()())”$ 均为有效括号子串，$“)(”、“(()”、“()())"$ 不是有效括号子串

样例1

输入

4
()()

输出

1

说明

$()()$ 为有效括号子串，需要处理一次

样例2

输入

6
((()()

输出

3