페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5798

Redistricting 2초 512MB

문제

Bovinopolis 대도시는 항상 두 주요 젖소 품종(홀스타인과 건지)이 정치적으로 경쟁하고 있다. 두 품종 모두 Bovinopolis 정부에서 충분한 영향력을 유지하고 싶어한다.

Bovinopolis의 대도시 지역은 N개의 목초지로 이루어진 일직선 형태이며, 각각의 목초지에는 한 마리의 젖소가 있다. 젖소는 홀스타인(H) 또는 건지(G) 둘 중 하나이다.

Bovinopolis 정부는 이 목초지를 여러 개의 연속된 구획으로 나누려고 한다. 각 구획은 최대 K개의 목초지를 포함할 수 있으며, 모든 목초지는 정확히 하나의 구획에 포함되어야 한다. 현재 정부는 홀스타인들이 장악하고 있기 때문에, 건지 우세 지역 또는 동점 지역이 최소화되는 방식으로 구획을 나누고 싶어한다.

• 구획에서 건지의 수가 홀스타인보다 많으면 그 구획은 건지 우세 지역이다.

• 구획에서 건지와 홀스타인의 수가 같다면 그 구획은 동점 지역이다.

이에 맞서, 건지 젖소들의 연합은 최악의 시나리오에서 건지 우세 지역 또는 동점 지역의 최소 개수가 얼마인지 알고 싶어한다. 이를 구하라.


입력

첫 번째 줄에 두 개의 정수 NK가 공백으로 구분되어 주어진다.

두 번째 줄에 길이 N의 문자열이 주어지며, 각 문자는 ‘H’(홀스타인) 또는 ‘G’(건지)이다.

제한 조건

1 \leq N \leq 300,000

1 \leq K \leq N


출력

건지 우세 지역 또는 동점 지역의 최소 개수를 출력하라.


예제1

입력
7 2
HGHGGHG
출력
3

출처

USACO 2019 January Platinum

역링크 공식 문제집만