[소프티어 6279번] 스마트 물류

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

import sys

input = sys.stdin.readline

# P - 로봇, H - 부품

n, k = map(int,input().split())

area = list(input())

visited = [False]*n

for i,value in enumerate(area):

    if value == 'P':
        for j in range(i-k,i+k+1):
            if 0 <= j < n and not visited[j] and area[j] == 'H':
                if i == j:
                    continue
                visited[j] = True
                break

print(len([x for x in visited if x == True] ))

 

이번 문제는 로봇과 부품으로 이루어진 1차원 배열에서 로봇이 자신을 기준으로 k 거리만큼의 부품을 집을 수 있다고 했을 때, 부품을 집을 수 있는 로봇의 최대 수를 구하는 문제이다.

 

처음에는 DFS를 사용하여 풀이하려고 했는데, 생각보다 완전탐색이 쉽지 않아 풀이를 참고하였다.

 

그 결과 왼쪽에서부터 부품을 수집하게 되면 오른쪽의 로봇들이 다른 로봇의 영향을 최대한 덜 받으면서, 많은 부품을 수집할 수 있다는 원리를 바탕으로 Greedy하게 풀이할 수 있었다.