백준 - 햄버거 분배 / Silver 3 / 19941번 / Python

문제 📋

백준 - 햄버거 분배

풀이 📝

import sys

n, k = map(int, sys.stdin.readline().split())
table = list(sys.stdin.readline())[:-1]
people = []
answer = 0

for i in range(n):
    if table[i] == 'P':
        people.append(i)

for person in people:
    for i in range(max(0, person - k), min(person + k + 1, n)):  # 먹을 수 있는 범위의 햄버거만 탐색.
        if table[i] == 'H':
            table[i] = 'N'
            answer += 1
            break
print(answer)

어렵지 않은 그리디 문제였다.
사람과 햄버거를 일렬로 늘어놓고 햄버거를 먹을 수 있는 최대 사람 수를 구하는 문제였다.

먼저 'P'인 위치들만 모아서 people 리스트에 모아주었다.
그런 다음 사람들의 위치를 순회하면서 각 사람들에 대해 +-K 구간을 왼쪽부터 탐색하면서 햄버거를 하나씩 소비시켰다.

왼쪽부터 탐색한 이유는 people 리스트가 정렬되어있는 사람들의 위치이기 때문에
최대한 왼쪽에 있는 햄버거를 먹어서 다음 사람이 햄버거를 먹을 수 있는 확률을 높여주기 위해서다.