[코테] 백준 그리디 19941번 문제

19941번 : 햄버거 분배

문제 링크

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

문제 설명

기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 K 이하인 햄버거를 먹을 수 있다.

햄버거	사람	햄버거	사람	햄버거	사람	햄버거	햄버거	사람	사람	햄버거	사람
1	2	3	4	5	6	7	8	9	10	11	12

위의 상태에서 K = 1인 경우를 생각해보자. 이 경우 모든 사람은 자신과 인접한 햄버거만 먹을 수 있다. 10번의 위치에 있는 사람은 11번 위치에 있는 햄버거를 먹을 수 있다. 이 경우 다음과 같이 최대 5명의 사람이 햄버거를 먹을 수 있다.

• 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
• 4번 위치에 있는 사람: 5번 위치에 있는 햄버거
• 6번 위치에 있는 사람: 7번 위치에 있는 햄버거
• 9번 위치에 있는 사람: 8번 위치에 있는 햄버거
• 10번 위치에 있는 사람: 11번 위치에 있는 햄버거

• 12번 위치에 있는 사람: 먹을 수 있는 햄버거가 없음   K = 2인 경우에는 6명 모두가 햄버거를 먹을 수 있다.

• 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
• 4번 위치에 있는 사람: 3번 위치에 있는 햄버거
• 6번 위치에 있는 사람: 5번 위치에 있는 햄버거
• 9번 위치에 있는 사람: 7번 위치에 있는 햄버거
• 10번 위치에 있는 사람: 8번 위치에 있는 햄버거
• 12번 위치에 있는 사람: 11번 위치에 있는 햄버거

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

입력

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

출력

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

문제 풀이

# N(식탁의 길이), K(햄버거를 선택할 수 있는 거리) 입력
N, K = map(int, input().split())
string = input()

count = 0 
last_p_index = 0
last_h_index = 0 

# 문자열에서 P를 못찾을때까지 반복
while string.find('P', last_p_index) > -1: 
    last_p_index = string.find('P', last_p_index)
         
    # p index에서 -K ~ +K의 범위의 문자열을 조회하기 위해
    st_index = last_p_index - K
    end_index = last_p_index + K + 1
    
    # 만약 st_index가 음수면 0으로 만들어줌 (find 함수를 쓸 때 음수부터 시작하면 끝에서부터 조회하기 떄문)
    if st_index < 0 : st_index = 0
    
    # 버거를 찾기 위한 시작 index 설정, 음수면 0으로 만들어줌
    st_find_index = last_h_index - st_index
    if st_find_index < 0 : st_find_index = 0
        
    # 버거의 index 확인
    find_burger = string[st_index:end_index].find('H', st_find_index)
    
    # 버거를 찾으면 count + 1, 마지막 햄버거 index + 1 저장
    if find_burger > -1 :
        count += 1
        last_h_index = find_burger + st_index + 1
        
    # 마지막 사람 index + 1, 그래야 이번에 찾은 사람 이후부터 조회 가능        
    last_p_index += 1
    
print(count)