[백준19941번] 햄버거 분배 - (python)

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

📌 문제 탐색하기

 

이 문제에서 구해야 하는 햄버거를 먹을 수 있는 최대 사람의 수 는 어떻게 구할 수 있을까

이 문제의 작은 단계에서 최적의 해는 가장 왼쪽에 존재하는 햄버거를 먹는 것이다. 앞에 사람이 가능한 왼쪽 햄버거를 먹어야 뒤에 사람의 선택지가 늘어나기 때문이다.

따라서 한 사람씩 차례로 왼쪽에 있는 햄버거를 먹고 왼쪽에 햄버거가 없는 경우 오른쪽에 있는 햄버거를 먹는다.

 

📌 코드 설계하기

배열을 순차적으로 돌면서 사람을 발견할 경우 그 왼쪽 위치에 있는 햄버거를 탐색하고 햄버거를 발견한 경우 햄버거를 먹은 사람을 +1 증가시키고 해당 햄버거를 먹은 햄버거 처리한다. 왼쪽에서 먹을 햄버거가 없는 경우 오른쪽을 탐색한다. 

1. N,K 값을 입력받는다.

2. 배열을 순차적으로 돌면서 사람에 위치인 경우 햄버거를 찾는다.

3. 햄버거를 찾는 함수를 구현한다. 

    3-1. 자신의 왼쪽부터 k범위 이내에 거리에서 햄버거를 탐색한다. 찾으면 찾은 위치를 표시하고 함수를 종료한다.

    3-2. 자신의 오른쪽부터 k범위 이내에 거리에서 햄버거를 탐색한다. 찾으면 찾은 위치를 표시하고 함수를 종료한다.

 

📌 코드

import sys
input = sys.stdin.readline

# 1. 입력 값을 받는다.
N,k = map(int,input().split())
arr = list(input())
ans = 0

def eat(x):
    global k
    global ans
    # 자신보다 왼쪽에 있는 햄버거 찾기
    for i in range(k,0,-1):
        if x-i>=0:
            if arr[x-i]=='H':
                arr[x-i]='X'
                ans+=1
                return

    # 자신보다 오른쪽에 있는 햄버거 찾기
    for i in range(1,k+1):
        if x+i<N:
            if arr[x+i]=='H':
                arr[x+i]='X'
                ans+=1
                return


for i in range(N):
    if arr[i]=='P':
        eat(i)

print(ans)