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

 

📌문제 탐색하기

• 길이 N인 벤치 모양의 식탁에 사람들과 햄버거가 단위 간격으로 놓여있름
  • 사람들은 자신의 위치에서 거리가 K 이하인 햄버거를 먹을 수 있음
• 식탁의 길이 N, 햄버거를 선택할 수 있는 거리 K, 사람과 햄버거의 위치가 주어졌을 때, 햄버거를 먹을 수 있는 사람의 최대 수

해당 문제는 '최대한 많은 사람이 햄버거를 먹을 수 있도록 하는 방법'을 찾는 것이 핵심이다. 왼쪽 사람부터 먹을  햄버거를 선택할 때, 최대한 더 많이 뒤에 남은 사람들이 햄버거를 먹을 수 있도록 선택하면 된다. 즉, 맨 앞 사람부터 마지막 사람까지 그리디하게 햄버거를 선택하면 된다.

맨 왼쪽 사람부터 햄버거를 먹는 경우, 뒷사람이 선택할 수 있는 햄버거를 최대한 많이 남기는 방법은 '햄버거를 선택 가능한 구간에서 맨 왼쪽에 놓인 햄버거를 먹는 것'이다. 예를 들어 K가 2이고, 햄버거와 사람이 HHHPPPH와 같이 나열되어 있으면 첫번째 사람은 HHHPPPH 이렇게 볼드 처리된 위치의 햄버거를 먹을 수 있다. 여기서 가장 왼쪽의 햄버거, 즉 2번 위치의 햄버거를 먹으면 가장 최적으로 햄버거를 선 택하는 것이다.

시간 복잡도는 (테이블의 각 요소를 순회)x(i번째 위치의 사람에 대해서 [i-k,i+k] 구간에 햄버거 있는지 탐색) = O(N)xO(2K) 이므로 O(NK)로 시간내에 풀이가 가능하다.

 

 

---

📌코드 설계하기

1. 식탁의 길이 N, 햄버거를 선택할 수 있는 거리 K 입력받기
2. 햄버거와 사람의 배치 table 리스트로 입력받기
3. 햄버거를 먹은 사람 수를 저장할 h_cnt 변수 0으로 초기화
4. 가장 왼쪽에 위치한 사람부터 순차적으로 탐색하면서, 해당 위치 i에서 [i-k, i+k] 구간 중 남은 햄버거가 있다면 가장 왼쪽에 있는 햄버거를 선택해서 선택되었다는 의미로 S로 바꿔주고 h_cnt를 1 증가시킨다
5. 모든 사람에 대한 탐색이 끝나면 h_cnt를 출력한다.

 

---

📌정답 코드

N, K = map(int, input().split())
table = list(input())
h_cnt = 0

for i in range(N):
    if table[i] == 'P':
        for j in range(i-K, i+K+1):
            if 0 <= j < N and table[j] == 'H':
                table[j] = 'S'
                h_cnt += 1
                break

print(h_cnt)