백준 19941번 - 햄버거 분배

햄버거 분배 문제 바로 가기

풀이 날짜: 2026-01-19

baekjoon 알고리즘 문제 풀이

풀이 코드

import sys
input = sys.stdin.readline

n,k = map(int, input().split())
data = list(input())
count = 0

for i in range(n):
    if data[i] == "P":
        for j in range(i-k,i+k+1):
            if 0<=j<n and data[j] == "H":
                count+=1
                data[j] = "0"
                break

print(count)
  

문제 접근

이 문제는 사람(P)이 주어졌을 때, 각 사람이 자신 기준 좌우 k 거리 안에서 햄버거(H)를 하나씩 먹을 수 있을 때 먹을 수 있는 최대 개수를 구하는 그리디 문제다. 핵심은 “각 사람에게 가능한 한 하나만 배정”하는 것이며, 이미 먹힌 햄버거는 다시 먹을 수 없도록 처리해야 한다.

구현 방식(그리디 + 선형 스캔)

코드는 왼쪽부터 i=0..n-1로 돌면서, data[i]가 P인 경우에만 그 사람의 먹을 수 있는 범위 [i-k, i+k]를 탐색한다. 범위 안에서 햄버거(H)를 발견하면 그 즉시 카운트를 올리고, 그 햄버거는 “소비됨” 표시를 한 뒤 다음 사람으로 넘어간다.

“먹힌 햄버거” 처리 방법

햄버거가 한 번 먹히면 다시 먹히면 안 되므로, 실제로 data[j] = “0”처럼 값을 바꿔서 “이미 사용됨” 상태로 만든다

헷갈렸던 점 정리

break가 왜 필수였는가 (틀렸던 이유)

처음에 break를 쓰지 않으면, 한 사람(P)이 범위 안에서 햄버거를 여러 개 발견할 때마다 연속해서 먹어버리는 상황이 생긴다. 하지만 문제 조건은 “사람 1명당 햄버거 1개”이므로, 한 사람이 첫 햄버거를 먹은 순간 그 사람에 대한 처리는 끝나야 한다. 따라서 햄버거를 하나 찾는 즉시 count += 1 하고 data[j]를 사용 처리한 다음 반드시 break로 반복문을 종료해야 한다.