괄호 분할

시간 제한7초메모리 제한1024 MB

요약

길이 n인 괄호 문자열을 연속된 k개의 구간으로 나눌 때, 각 구간의 올바른 괄호 부분문자열 개수 합의 최솟값을 구합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 이분 탐색, 누적 합
정답자: 아직 제출이 없습니다

문제

괄호 식의 정의는 다음과 같다:

() 는 올바른 괄호 식이다.
S가 올바른 괄호 식이면 (S)도 올바른 괄호 식이다.
S1과 S2가 올바른 괄호 식이면 S1S2도 올바른 괄호 식이다.
위 규칙으로 만들 수 없는 문자열은 올바른 괄호 식이 아니다.

'('와 ')'로만 이루어진 문자열의 괄호성은 그 문자열의 부분 문자열 중 올바른 괄호 식인 것의 개수이다. 같은 부분 문자열이 여러 번 나오면 나온 횟수만큼 센다.

길이가 $n$ 인 문자열이 주어진다. 이 문자열은 '('와 ')'로만 이루어져 있으며, 올바른 괄호 식이 아닐 수도 있다. 이 문자열을 공백이 없는 $k$ 개의 구간으로 나누어라. 각 문자는 정확히 하나의 구간에 속해야 한다. 나뉜 문자열들의 괄호성 합이 최소가 되도록 나누어라.

입력

첫째 줄에 문자열의 길이 $n$ 과 나눌 구간의 수 $k$ 가 주어진다 (1 ≤ k ≤ n ≤ 100 000).

둘째 줄에 길이 $n$ 의 문자열이 주어진다. 문자열은 '('와 ')'로만 이루어져 있다.

출력

최적으로 나눴을 때 $k$ 개 문자열 괄호성 합의 최솟값을 한 줄에 출력한다.

예제2

예제 1
입력
```
15 2
())(()())()(())
```
예상 출력
```
6
```
예제 2
입력
```
15 3
())(()())()(())
```
예상 출력
```
3
```