[알고리즘|파이썬] 백준 19941 햄버거 분배

문제 링크: https://www.acmicpc.net/problem/19941

📌 문제 탐색하기

시간 제한: 0.5초 (추가 시간 없음)
메모리 제한: 256 MB

 

✏️ 구해야 하는 정답

예시

사람들은 자신의 위치에서 거리가 K 이하인 햄버거를 먹을 수 있다.

K = 1, 최대 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, 사람과 햄버거의 위치가 주어졌을 때, 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.

 

조건

- 1 ≤ N ≤ 20,000

- 1 ≤ k ≤ 10

 

 

---

📌 풀이하기

그리디 알고리즘을 사용할 수 있을까?

그리디 알고리즘이란?

그리디 알고리즘은 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 각 단계에서 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행해 최종적인 답에 도달하는 알고리즘이다. 조금 더 풀어 설명하면 지금 당장 가질 수 있는 최고의 이익을 따라 가는 알고리즘이라 할 수 있다.

항상 최적의 값을 보장하지 않으며, 최적의 값의 근사한 값을 목표로 하는 알고리즘이다.

그리디 알고리즘의 속성

1. 탐욕 선택 속성

앞의 선택이 이후의 선택에 영향을 주지 않는 경우를 뜻함.

2. 최적 부분 구조

전체 문제의 최적의 해가 부분 문제의 최적의 해로 구성 될 수 있는 경우를 뜻함.

 

그리디 알고리즘으로 구현할 수 있을까?

이 문제는 작은 문제로 쪼개서 각 문제의 해를 찾고, 그 해를 모아 전체 해답이 될 수 있으며, 이때 앞의 선택이 이후의 선택에 영향을 주지 않는다. 그렇기 때문에 그리디 알고리즘을 선택하여 문제를 풀 수 있다.

 

햄버거를 먹을 수 있는 사람의 수를 어떻게 구할까?

예시 1.

N = 20, K = 1

HHPHPPHHPPHPPPHPHPHP 의 경우를 생각해보자.

 

H HP HP PH HP PH PP PH PH PH P 

 

K = 1 이므로 P는 앞뒤에 있는 H와 매칭이 될 수 있다.

같은 색으로 묶인 것이 햄버거를 먹은 사람이라고 표현할 수 있으므로, 이 경우 최대 8명이 햄버거를 먹을 수 있다.

 

예시 2.

N = 20, K = 2

HHHHHPPPPPHPHPHPHHHP 의 경우도 생각해보자.

 

K = 2이므로 3개씩 묶어서 생각을 해볼 수 있다.

 

HHH HHPPPPPHPHPHPHHHP

H HHH HPPPPPHPHPHPHHHP

HH HHH PPPPPHPHPHPHHHP

HHH HHP PPPPHPHPHPHHHP

HHHH HPP PPPHPHPHPHHHP

HHHHH PPP PPHPHPHPHHHP

...

HHHHHPPPPPHPHPHPH HHP

 

색깔로 묶어둔 3개를 생각했을때, 이 묶음 안에 H, P 가 하나씩 들어있다면 햄버거를 먹는 사람이 생긴다고 볼 수 있다.

묶음 중 H, P 가 하나 이상씩 들어 있다면 햄버거 먹는 사람 카운트를 하나 올리고, H, P 는 다시 사용될 수 없게 다른 값으로 바꾸면 답을 구할 수 있다.

 

단계 별로 살펴보자. 

 

HHH HHPPPPPHPHPHPHHHP    -> 없음

H HHH HPPPPPHPHPHPHHHP   -> 없음

HH HHH PPPPPHPHPHPHHHP   -> 없음

HHH HHP PPPPHPHPHPHHHP   -> 햄버거 먹는 사람 카운트 = 1, 사용된 H, P 값은 0으로 변경

HHH0 H0P PPPHPHPHPHHHP   -> 햄버거 먹는 사람 카운트 = 2, 사용된 H, P 값은 0으로 변경

HHH00 0PP PPHPHPHPHHHP   -> 없음

HHH000 PPP PHPHPHPHHHP   -> 없음

HHH000P PPP HPHPHPHHHP   -> 없음

HHH000PP PPH PHPHPHHHP   -> 햄버거 먹는 사람 카운트 = 3, 사용된 H, P 값은 0으로 변경

HHH000PP0 P0P HPHPHHHP   -> 없음

HHH000PP0P 0PH PHPHHHP   -> 햄버거 먹는 사람 카운트 = 4, 사용된 H, P 값은 0으로 변경

HHH000PP0P0 00P HPHHHP   -> 없음

HHH000PP0P00 0PH PHHHP    -> 햄버거 먹는 사람 카운트 = 5, 사용된 H, P 값은 0으로 변경

HHH000PP0P000 00P HHHP    -> 없음

HHH000PP0P0000 0PH HHP    -> 햄버거 먹는 사람 카운트 = 6, 사용된 H, P 값은 0으로 변경

HHH000PP0P00000 00H HP    -> 없음

HHH000PP0P000000 0HH P    -> 없음

HHH000PP0P0000000 HHP     -> 햄버거 먹는 사람 카운트 = 7, 사용된 H, P 값은 0으로 변경

---

📌 코드 설계하기

1. n, k, hp_list input으로 받기

2. count = 0 초기화

3. hp_list 의 배열을 돌면서 k+1개의 묶음을 만듦

  - 묶음에 H와 P가 있는지 확인

  - 묶음에 있는 첫번째 H, 첫번째 P를 0으로 수정

  - count += 1

4. count 출력

 

---

📌 정답 코드

n, k = map(int, input().split())

hp_list = list(input())
count = 0

for i in range(0, n-k, 1):
    cut = hp_list[i:i+k+1]
    if 'H' in cut and 'P' in cut:
        h_idx = cut.index('H')
        p_idx = cut.index('P')
        hp_list[i+int(h_idx)] = '0'
        hp_list[i+int(p_idx)] = '0'
        count += 1
print(count)