[백준 알고리즘] 백준 19941번 햄버거 분배 파이썬(Python)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 19941번 햄버거 분배 파이썬(Python)

1) 문제번호 : 19941번

 

2) 문제 출처

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

19941번: 햄버거 분배

 

2. 문제

기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 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, 사람과 햄버거의 위치가 주어졌을 때, 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.

 

3. 제약사항

 

 

4. 입력

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

 

5. 출력

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

 

6. 풀이

- 리스트로 입력 받아서, 사람이 있으면 현재 위치에서 i-K, i+K 이 사이의 처음부터 햄버거가 있으면 햄버거를 먹은 사람의 수를 1 증가시키고, 햄버거를 먹었으니 없다는 의미로 nothing을 넣어준다.

 

7. 소스 코드

import sys
input = sys.stdin.readline

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

li = list(input().rstrip()) # 식탁 입력

count = 0 # 먹은 사람 수

for i in range(len(li)) :
    if li[i] == "P" :
        for j in range(i-K, i+K+1) :
            if 0 <= j < N and li[j] == "H" : # 햄버거면
                count += 1 # 먹는 사람 1 증가
                li[j] = "nothing" # 먹었으니 없애준다.
                break

print(count)

 

---