판치기

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

요약

H와 T로 이루어진 동전 배열이 주어질 때, 매번 서로 다른 K개의 동전을 뒤집어 모든 동전을 T로 만드는 최소 횟수를 구하고, 불가능하면 -1을 출력한다.

문제

(N)개의 동전을 바닥에 놓고, 임의의 동전을 뒤집는 것을 반복해 모두 뒷면이 보이는 상태로 바꾸면 이기는 게임이다.

판치기 경력 20년의 치훈이는 판치기 최고의 기술인 "(K)-뒤집기"를 익혔다. "(K)-뒤집기"는 서로 다른 (K)개의 동전을 한 번에 뒤집는 기술이다.

초기 동전의 상태가 주어진다. "(K)-뒤집기"만 사용해 게임을 이기려면 최소 몇 번 사용해야 할까?

첫째 줄에 (N), (K)가 주어진다.

둘째 줄에 초기 동전의 상태를 나타내는 문자열 (S)가 주어진다.

(S)의 (i)번째 문자가 'H'면 (i)번째 동전이 앞면, 'T'면 (i)번째 동전이 뒷면이 보이는 상태다.

첫째 줄에 문제의 답을 출력한다.

모두 뒷면이 보이는 상태로 바꿀 수 없다면 대신 -1을 출력한다.