서론

그리디 문제입니다.
n의 범위가 20,000 이하이고 k의 범위가 10이하이기 때문에,
모두 탐색해도 20만번밖에 연산을 안하여 무지성으로 탐색해도 쉽게 통과할 수 있는 문제입니다.

난이도

실버 3

---

문제

조건

시간 제한	메모리 제한
0.5 초 (추가 시간 없음)	256 MB

---

기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가
$K$ 이하인 햄버거를 먹을 수 있다.

햄버거	사람	햄버거	사람	햄버거	사람	햄버거	햄버거	사람	사람	햄버거	사람
1	2	3	4	5	6	7	8	9	10	11	12

위의 상태에서 $K = 1$인 경우를 생각해보자. 이 경우 모든 사람은 자신과 인접한 햄버거만 먹을 수 있다. 10번의 위치에 있는 사람은 11번 위치에 있는 햄버거를 먹을 수 있다. 이 경우 다음과 같이 최대 5명의 사람이 햄버거를 먹을 수 있다.

2번 위치에 있는 사람: 1번 위치에 있는 햄버거
4번 위치에 있는 사람: 5번 위치에 있는 햄버거
6번 위치에 있는 사람: 7번 위치에 있는 햄버거
9번 위치에 있는 사람: 8번 위치에 있는 햄버거
10번 위치에 있는 사람: 11번 위치에 있는 햄버거
12번 위치에 있는 사람: 먹을 수 있는 햄버거가 없음

$K = 2$인 경우에는 6명 모두가 햄버거를 먹을 수 있다.

2번 위치에 있는 사람: 1번 위치에 있는 햄버거
4번 위치에 있는 사람: 3번 위치에 있는 햄버거
6번 위치에 있는 사람: 5번 위치에 있는 햄버거
9번 위치에 있는 사람: 7번 위치에 있는 햄버거
10번 위치에 있는 사람: 8번 위치에 있는 햄버거
12번 위치에 있는 사람: 11번 위치에 있는 햄버거

식탁의 길이 $N$, 햄버거를 선택할 수 있는 거리 $K$, 사람과 햄버거의 위치가 주어졌을 때, 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.

---

입력

첫 줄에 두 정수 $N$과 $K$가 있다. 그리고 다음 줄에 사람과 햄버거의 위치가 문자 P(사람)와 H(햄버거)로 이루어지는 길이 $N$인 문자열로 주어진다.

---

출력

첫 줄에 햄버거를 먹을 수 있는 최대 사람 수를 나타낸다.

---

제한

• $1 \le N \le 20,000$ 

• $1 \le K \le 10$ 

---

예시

예제 입력 1

20 1
HHPHPPHHPPHPPPHPHPHP

예제 출력 1

8

예제 입력 2

20 2
HHHHHPPPPPHPHPHPHHHP

예제 출력 2

7

---

풀이

1. s에 햄버거의 위치와 사람의 위치를 저장한다.
2. s를 순차적으로 탐색하며 현재 위치가 사람인 경우, 좌우로 k만큼을 탐색하며 햄버거가 있는지 탐색한다.
3. 현재 위치에서 k만큼 떨어진 위치가 0과 n의 사이(배열 범위 내)면서 햄버거가 있다면,
   햄버거가 있는 곳의 값을 -1로 바꾸고 ans를 1 증가한다.
   (-1은 햄버거가 먹혔다는 것을 의미한다.)

코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
# 입력 받은 문자열에서 H(햄버거)는 0, P(사람)는 1로 바꾸어 s에 저장
s = list(map(lambda x: 0 if x == 'H' else 1, input().rstrip()))
ans = 0	# 햄버거를 먹은 사람 수

for i in range(n):
    if s[i] == 1:							# 현재 인덱스(i)가 사람이라면
        for j in range(i - k, i + k + 1):	# 좌우로 k만큼 떨어진 거리를 탐색
            if 0 <= j < n and s[j] == 0:	# 현재 위치(j)가 범위 내에 있고 햄버거라면
                s[j] = -1					# 현재 위치의 값을 -1
                ans += 1					# 햄버거를 먹은 사람 수 증가
                break						# 다음 인덱스로 이동

print(ans)

실행 결과