[백준/19941] 햄버거 분배 (Python)

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

19941번: 햄버거 분배

 

Difficulty : Silver 3

 

Status : Solved

 

Time : 00:04:14

 

---

 

문제 설명

 

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

 

위의 상태에서 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인 문자열로 주어진다.

 

출력

 

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

 

입력 예시

 

20 1
HHPHPPHHPPHPPPHPHPHP

 

출력 예시

 

8

 

 

---

 

풀이

 

왼쪽부터 오른쪽으로 탐색한다고 가정할 때, 왼쪽의 사람부터 범위 내에서 자신이 먹을 수 있는 가장 왼쪽의 햄버거를 먹으면 최적해가 된다. 즉 그리디로 탐색을 진행하도록 하자. 

 

풀이 코드

N, K = map(int, input().split())
visited = [False]*N
map_list = input().strip()
answer = 0
for i in range(N) :
  if map_list[i] == 'H' :
    continue
  for j in range(i-K, i+K+1) :
    if not -1 < j < N :
      continue
    if map_list[j] == 'H' and not visited[j] :
      visited[j] = True
      answer += 1
      break
print(answer)

풀이 완료!