선거구 재획정

시간 제한2초메모리 제한512 MB

요약

H와 G로 이루어진 소들의 줄을 길이 K 이하의 연속한 선거구로 나눌 때, G가 H보다 많거나 같은 선거구의 수를 최소로 만드는 값을 구한다.

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

문제

소 메가시티 보비노폴리스가 선거구를 다시 나누려 한다. 이 도시에는 두 주요 소 품종인 홀스타인과 건지가 살고 있는데, 두 품종 모두 보비노폴리스 정부에서 충분한 영향력을 유지하려 하기 때문에 이 과정은 언제나 첨예하게 갈린다.

보비노폴리스 대도시권은 일직선으로 늘어선 $N$ 개의 목초지로 이루어져 있다( $1 \leq N \leq 3 \cdot 10^5$ ). 각 목초지에는 소가 한 마리씩 있고, 그 소는 홀스타인이거나 건지이다.

보비노폴리스 정부는 대도시권을 여러 개의 연속한 선거구로 나누려 한다. 각 선거구에는 목초지가 최대 $K$ 개까지 들어갈 수 있고( $1 \leq K \leq N$ ), 모든 목초지는 정확히 하나의 선거구에 속한다. 현재 정부는 홀스타인이 장악하고 있으므로, 건지가 다수이거나 동수인 선거구의 수를 최소로 만드는 재획정 방법을 찾으려 한다. 건지와 홀스타인의 수가 같으면 동수 선거구이다.

걱정하는 건지 연합은 정부의 재획정이 얼마나 큰 피해를 줄 수 있는지 알아보려 한다. 건지가 다수이거나 동수인 선거구 수의 최악의 경우에 대한 최솟값을 구하도록 돕자.

입력

첫째 줄에 공백으로 구분된 두 정수 $N$ 과 $K$ 가 주어진다. 둘째 줄에 길이 $N$ 의 문자열이 주어진다. 각 문자는 홀스타인이면 'H', 건지이면 'G'이다.

출력

건지가 다수이거나 동수인 선거구 수의 가능한 최솟값을 출력한다.

예제1

예제 1
입력
```
7 2
HGHGGHG
```
예상 출력
```
3
```