백준 | 햄버거 분배

백준 햄버거 분배

아래의 이유에서 그리디 알고리즘으로 접근했다.

왼쪽에서 오른쪽으로 순차 탐색하면, i번째에 위치한 사람이 [i - k, i + k] 범위에서 가장 왼쪽에 위치한 햄버거(인덱스 값이 가장 작은 것)를 먹을 경우, 이후 사람들이 선택 가능한 햄버거 개수가 최대가 된다.

1인당 하나의 햄버거만 먹을 수 있으므로, 각 사람의 선택은 독립적으로 이뤄진다.

이는 부분 최적 구조를 만족한다고 할 수 있다.

import sys

# 입력
n, k = map(int, sys.stdin.readline().split())
arr = list(sys.stdin.readline().strip())

# cnt: 햄버거를 먹을 수 있는 사람의 최대 수
cnt = 0
for i in range(n):
    if arr[i] == 'P':
        for j in range(max(0, i - k), min(n, i + k + 1)):
            if arr[j] == 'H':
                arr[j] = 'X'
                cnt += 1
                break

# 출력
print(cnt)