문제

https://www.acmicpc.net/problem/19941

문제접근

예전에 비슷한 문제를 본 적이 있다. 그 문제의 조건은 인접한 것만 선택할 수 있다였고 그 당시 왼쪽부터 선택하고 왼쪽이 없으면 오른쪽을 선택하면 최대한 많은 선택을 할 수 있었다.
그 문제에서 아이디어를 얻어왔다.
대신 여기선 k라는 범위가 있었는데 똑같이 사람을 기준으로 왼쪽에서 k만큼 오른쪽에서 k만큼이라는 범위가 있을 때 가장 왼쪽부터 선택 가능성을 따지면 최대한 많은 사람이 선택 가능한 것으로 보였다.

주의깊게 생각해야 할 부분은 앞선 사람이 오른쪽을 선택 뒤쪽 사람이 왼쪽을 선택.... 그림 그려서 올리기

코드

from sys import stdin

input = stdin.readline

n, k = map(int, input().split())
tmp = input()
s = []
for i in tmp:
    s.append(i)
ans = 0
for i in range(n):
    if s[i] == "P":
        eat_range = [max(0, i - k), min(n - 1, i + k)]
        for j in range(eat_range[0], eat_range[1] + 1):
            if s[j] == "H":
                ans += 1
                s[j] = "0"
                break
print(ans)

복잡도 분석

시간 복잡도

채점결과 : 80ms

공간 복잡도

채점 결과 : 31120KB

학습포인트