[BOJ] 19941 햄버거 분배(python)

허치영·2022년 3월 9일
0

BOJ 알고리즘

목록 보기
5/26
post-thumbnail

문제

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

햄버거사람햄버거사람햄버거사람햄버거햄버거사람사람햄버거사람
123456789101112

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

2번 위치에 있는 사람: 1번 위치에 있는 햄버거
4번 위치에 있는 사람: 5번 위치에 있는 햄버거
6번 위치에 있는 사람: 7번 위치에 있는 햄버거
9번 위치에 있는 사람: 8번 위치에 있는 햄버거
10번 위치에 있는 사람: 11번 위치에 있는 햄버거
12번 위치에 있는 사람: 먹을 수 있는 햄버거가 없음
K=2K = 2인 경우에는 6명 모두가 햄버거를 먹을 수 있다.

2번 위치에 있는 사람: 1번 위치에 있는 햄버거
4번 위치에 있는 사람: 3번 위치에 있는 햄버거
6번 위치에 있는 사람: 5번 위치에 있는 햄버거
9번 위치에 있는 사람: 7번 위치에 있는 햄버거
10번 위치에 있는 사람: 8번 위치에 있는 햄버거
12번 위치에 있는 사람: 11번 위치에 있는 햄버거
식탁의 길이 NN, 햄버거를 선택할 수 있는 거리 KK, 사람과 햄버거의 위치가 주어졌을 때, 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

풀이

풀이를 생각해내고 너무 무식한 방법인 것 같아서 분류를 보니 역시 그리디였다.
단순하게 사람이 위치한 인덱스에 가면 해당 인덱스 ±  K\pm \; K 범위 내의 맨 앞 햄버거를 없애가는 식으로 하면 된다.

import sys

len_table, dist_ham = map(int, sys.stdin.readline().split())
table_stat = list(map(str, sys.stdin.readline().rstrip()))

num_eat = 0
for i in range(len_table):
	# 사람 위치한 인덱스에 오면
    if table_stat[i] == 'P':
    	# 선택 가능한 범위 min_idx, max_idx로 지정
        min_idx = max(0, i-dist_ham)
        max_idx = min(len_table-1, i+dist_ham)
        # 가장 앞에 있는 햄버거 없애줌
        for k in range(min_idx, max_idx+1):
            if table_stat[k] == 'H':
                table_stat[k] = 'X'
                num_eat += 1
                break
print(num_eat)
profile
NLP를 공부하는 대학생입니다

0개의 댓글