레이팅 미적용아마 "가위바위보" 게임을 들어 본 적이 있을 것이다. 소들은 이와 비슷한 "발굽, 종이, 가위"라는 게임을 즐겨 한다.
"발굽, 종이, 가위"의 규칙은 간단하다. 두 마리의 소가 서로 대결한다. 둘은 셋을 센 뒤 동시에 발굽, 종이, 가위 중 하나를 나타내는 동작을 취한다. 발굽은 가위를 이기고(발굽으로 가위를 부술 수 있으므로), 가위는 종이를 이기며(가위로 종이를 자를 수 있으므로), 종이는 발굽을 이긴다(발굽이 종이에 베일 수 있으므로). 예를 들어 첫 번째 소가 "발굽" 동작을 하고 두 번째 소가 "종이" 동작을 하면 두 번째 소가 이긴다. 물론 두 소가 같은 동작을 하면 비길 수도 있다.
농부 존은 자신의 자랑스러운 소 베시와 "발굽, 종이, 가위" 게임을 \(N\)판 하려고 한다 (\(1 \leq N \leq 100,000\)). 이 게임의 달인인 베시는 FJ가 동작을 취하기 전에 그의 동작을 모두 예측할 수 있다. 하지만 안타깝게도 베시는 소인지라 매우 게으르다. 그래서 같은 동작을 여러 번 연속으로 내는 경향이 있다. 실제로 베시는 전체 게임 동안 동작을 최대 \(K\)번만 바꾸려 한다 (\(0 \leq K \leq 20\)). 예를 들어 \(K=2\)라면, 처음 몇 판은 "발굽"을 내다가 한동안 "종이"로 바꾸고, 남은 판은 "발굽"을 내면서 끝낼 수 있다.
FJ가 낼 동작의 순서가 주어질 때, 베시가 이길 수 있는 게임 수의 최댓값을 구하시오.
문제 출처: Mark Chen, Brian Dean
문제 출처: Mark Chen, Brian Dean
입력 파일의 첫째 줄에 \(N\)과 \(K\)가 주어진다.
다음 \(N\)개의 줄에 FJ의 동작이 주어지며, 각각은 H, P, S 중 하나이다.
베시가 동작을 최대 \(K\)번만 바꿀 수 있을 때, 이길 수 있는 게임 수의 최댓값을 출력한다.
hps.in · 출력을 쓸 파일 hps.out5 1
P
P
H
P
S4