[Softeer] 스마트 물류

문제

요약

문자열 안에 P 로봇의 위치에서 k 간격 사이에 있는 H만 집을 수 있을 때,

H를 집을 수 있는 로봇 P의 최대 개수를 구하시오.

 

원본

https://softeer.ai/practice/6279

Softeer - 현대자동차그룹 SW인재확보플랫폼

풀이

처음에는 dfs로 풀었는데 최소 경우는 본인 위치에서 가장 먼 것을 골랐을 때이기 때문에

굳이 dfs로 모든 경우를 확인하기 보다는 가장 먼 위치의 하나를 고르면 최대 개수가 구해진다.

올바른 풀이에 근접하게 접근하는 실력은 많이 늘었는데

범위나 반복 break 조건 같은 부분만 더 신경 쓰면 될 것 같다.

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
S = list(input().strip())
answer = 0
visited = [0] * n
    
for i in range(n):
    if S[i] == "P":
        visited[i] = 1
        for j in range(i-k, i+k+1):
            if 0 <= j < n and visited[j] == 0 and S[j] == "H":
                visited[j] = 1
                answer += 1
                break

print(answer)