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

> Python, 그리디 알고리즘

 

 

 

 

 

 

 

 

📖 문제 : 햄버거 분배 (Python)

 

기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 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인 문자열로 주어진다.

 

 

출력

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

 

 

제한

•  1 ≤ N ≤ 20,000
•  1 ≤ K ≤ 10

 

 

예제 입력 1

20 1
HHPHPPHHPPHPPPHPHPHP

예제 출력 1

8

 

 

 

내 코드

import sys

input = sys.stdin.readline

if __name__ == "__main__":

    N, K = map(int, input().split())
    PH = input()
    PH = list(PH)
    answer = 0
    for i in range(len(PH)):
        if PH[i] == "P":
            for j in range(i - K, i + K + 1):
                if 0 <= j <= N - 1 and PH[j] == "H":
                    answer += 1
                    PH[j] = "H_EAT"
                    break

    print(answer)
    
    # for i in range(len(PH)):
    #     if PH[i] == "P":
    #         # left
    #         idx = K
    #         while i != idx:
    #             if PH[i - K] == "H" and i - K > 0:
    #                 PH[i - K] = "H_EAT"
    #                 answer += 1
    #                 break
    #             idx += 1
    #
    #         else:
    #             # right
    #             idx = i
    #             while i + K != idx:
    #                 idx += 1
    #                 if idx > N-1:
    #                     break
    #                 if PH[idx] == "H" and idx < N - 1:
    #                     PH[idx] = "H_EAT"
    #                     answer += 1
    #                     break
    #  print(answer)

 

 

Point ! ⭐️ 

• 그리디 문제인 만큼 각 단계의 최선방법이 결국 해결책이라는 것이므로 !
  왼쪽부터 사람의 위치를 판단해가며 가능한 '가장 왼쪽의 햄버거' 를 먹어야 남은 오른쪽 사람들이 먹을 수 있는 햄버거의 수가 많아진다는 것 !
  
  
• 주석 처리된 것은 왼쪽 오른쪽으로 나눠서 while문 돌리면서 탐색하는 방법이였는데, '시간초과' !
  for문을 사용해서 구간 반복을 할 수 있다는 생각을 웨 못했을까 ! 
  아이디어만 참고해서 다시 풀었슴당 >_<

 

 

 

 

 

 

백준

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

19941번: 햄버거 분배