이번 문제는 BFS를 통해 해결하였다. 동전의 앞면의 갯수와 뒷면의 갯수를 저장하고, 뒷면의 갯수로 방문처리를 진행하였다. 0~k개만큼 동전을 뒤집을 수 있으므로 앞면의 갯수와 뒷면의 갯수를 이용하여 다음 뒷면의 갯수를 구하고, 만약 뒷면의 갯수가 n일 경우 카운팅 변수를 반환하였다.

Code

from collections import deque
n, k = map(int, input().split())
coins = list(str(input()))
front, back = 0, 0
for i in range(n):
    if coins[i] == 'H':
        front += 1
    else:
        back += 1
def find_answer():
    q = deque()
    q.append((back, 0))
    visited = [0 for _ in range(n+1)]
    visited[back] = True
    while q:
        bk, cnt = q.popleft()
        if bk == n:
            return cnt
        ft = n-bk
        for i in range(k+1):
            turn_b, turn_f = i, k-i
            if turn_b > bk or turn_f > ft:
                continue
            nxt_bk = bk-turn_b+turn_f
            if not visited[nxt_bk]:
                visited[nxt_bk] = True
                q.append((nxt_bk, cnt+1))
    return -1
print(find_answer())