[PS] 햄버거 분배

Byeonggwan Kang·2023년 10월 23일

Problem Solving

목록 보기

6/10

https://www.acmicpc.net/problem/19941

문제 설명

기다란 벤치 모양의 식탁에 사람들과 햄버거가 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 $K$ 이하인 햄버거를 먹을 수 있다. (배열 요소의 양 옆의 거리는 1이다.)

식탁의 길이 $N$ , 햄버거를 선택할 수 있는 거리 $K$ , 사람과 햄버거의 위치가 주어졌을 때, 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.

입력

첫 줄에 두 정수 $N$ 과 $K$ 가 있다. 그리고 다음 줄에 사람과 햄버거의 위치가 문자 P(사람)와 H(햄버거)로 이루어지는 길이 $N$ 인 문자열로 주어진다.

출력

첫 줄에 햄버거를 먹을 수 있는 최대 사람 수를 나타낸다.

제한

$1 \le N \le 20,000$
$1 \le K \le 10$

예시 입출력

20 1
HHPHPPHHPPHPPPHPHPHP

8

문제 해결 방법

그리디 알고리즘으로 해결 가능하다.

배열의 왼쪽부터 탐색을 시작한다고 가정하자.

햄버거가 주위에 있는지 탐색할 때에도 왼쪽부터 탐색한다면 항상 정답을 구할 수 있다.

만약 먹은 햄버거가 다른 사람이 먹었어야만 하는 햄버거라면, 그 다른 사람은 항상 더 왼쪽에 있었어야 하기 때문이다.

시간복잡도는 O(NK)를 요구한다.

코드 구현

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
string = input()
check = [0 for _ in range(N)]
answer = 0

for i in range(N):
    if string[i] == 'P':
        left, right = max(0, i-K), min(N-1, i+K)
        for idx in range(left, right+1):
            if string[idx] == 'H' and check[idx] == 0:
                check[idx] = 1
                answer += 1
                break