통째로 비어 있는 주차 구역

문제

한 주차장은 여러 주차 구역을 작은 구역으로 나누어 관리한다. 하나의 구역 안에는 개별 주차 칸과 더 작은 구역이 순서대로 들어 있다. 작은 구역 안에도 다시 주차 칸이나 구역이 들어갈 수 있다. 관리실은 이러한 구조와 현재 주차 상태를 하나의 문자열로 기록한다. 빈 주차 칸 하나는 문자 0으로, 차가 있는 주차 칸 하나는 문자 1로 나타낸다. 구역 하나는 그 안에 직접 들어 있는 항목들의 기록을 순서대로 이어 붙인 뒤, 전체를 한 쌍의 괄호로 감싸서 나타낸다. 각 항목은 주차 칸 하나이거나 작은 구역 하나다. 모든 구역에는 항목이 적어도 하나 있으며, 주차장 전체도 하나의 구역으로 기록한다. 괄호는 구역의 경계만 나타내며 주차 칸으로 세지 않는다. 예를 들어 (0(00)1)은 전체 구역 안에 빈 칸 하나, 빈 칸 두 개로 이루어진 작은 구역 하나, 차가 있는 칸 하나가 차례로 있다는 뜻이다. 이때 전체 구역에 속한 주차 칸은 작은 구역의 칸까지 포함하여 네 개다. 작은 구역의 두 칸은 그 작은 구역에도 속하고 전체 구역에도 속한다. 관리자는 빈 구역을 통째로 빌려주려고 한다. 어떤 구역을 빌려주려면 그 구역에 속한 모든 주차 칸이 비어 있어야 하며, 주차 칸의 수가 주어진 정수 K 이상이어야 한다. 더 작은 구역에 들어 있는 주차 칸도 모두 이 조건을 검사할 때 포함한다. 서로 다른 괄호 쌍으로 표시된 구역은 포함하는 주차 칸이 같더라도 서로 다른 구역으로 센다. 전체 구역과 그 안의 작은 구역이 모두 조건을 만족하면 둘 다 센다. 여러 구역을 동시에 빌려줄 수 있는지는 고려하지 않고, 각 구역이 단독으로 조건을 만족하는지만 판단한다. 조건을 만족하는 구역의 개수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 K가 주어진다. 1 ≤ K ≤ 100,000이다.
둘째 줄에 주차장 기록 문자열 S가 주어진다. S의 길이는 3 이상 100,000 이하이며, 문자 0, 1, (, )로만 이루어진다. S는 지문에서 정의한 하나의 전체 구역을 나타내는 올바른 기록이다. 모든 구역은 하나 이상의 항목을 포함한다. 문자열에는 공백이 없다.

출력

조건을 만족하는 구역의 개수를 정수 하나로 출력한다. 조건을 만족하는 구역이 없으면 0을 출력한다.

2
(0(00)1)

1

2
(((00))(000))

4

1
(1(01)(11))

0

출처: Devin.KR 자체 제작