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

링크🔗

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

---

🗒️파이썬 코드 풀이

N,K = map(int,input().split())
lst = list(input())
cnt = 0
for i in range(N):
    if lst[i] == "P":
        for s in range(i-K,i+K+1):
            if 0<=s<N and lst[s] == "H":
                lst[s] = 0
                cnt += 1
                break
print(cnt)

 

1. 더 많은 사람들이 햄버거를 먹기위해서, 최대한 왼쪽부터 먹어줘야한다.

 

2. 우선 lst[i] = "P"일 때의 조건을 세팅해두고

 

3. s의 범위를 (i-k ~ i+k)로 해두고

 

4. 0 ≤ N <0 과 lst[s] = "H" 일 때 cnt를 올려주면 된다.

 

 

📌  문제 코멘트

범위 설정만 잘하면 어렵지 않은 문제이지만,

나는 저 범위 설정을 잘 못해서 시간이 오래 걸렸다 ...

내가 풀이했던 방식은 양쪽 큰 순서대로 처리하고, 여러 경우의 수를 생각햇는데,

복잡하고 옮지 못한 방법이였다. 

 

---

📚문제

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

햄버거	사람	햄버거	사람	햄버거	사람	햄버거	햄버거	사람	사람	햄버거	사람
1	2	3	4	5	6	7	8	9	10	11	12

위의 상태에서 𝐾=1 인 경우를 생각해보자. 이 경우 모든 사람은 자신과 인접한 햄버거만 먹을 수 있다. 10번의 위치에 있는 사람은 11번 위치에 있는 햄버거를 먹을 수 있다. 이 경우 다음과 같이 최대 5명의 사람이 햄버거를 먹을 수 있다.

• 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
• 4번 위치에 있는 사람: 5번 위치에 있는 햄버거
• 6번 위치에 있는 사람: 7번 위치에 있는 햄버거
• 9번 위치에 있는 사람: 8번 위치에 있는 햄버거
• 10번 위치에 있는 사람: 11번 위치에 있는 햄버거
• 12번 위치에 있는 사람: 먹을 수 있는 햄버거가 없음

 𝐾=2$K = 2$인 경우에는 6명 모두가 햄버거를 먹을 수 있다.

• 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
• 4번 위치에 있는 사람: 3번 위치에 있는 햄버거
• 6번 위치에 있는 사람: 5번 위치에 있는 햄버거
• 9번 위치에 있는 사람: 7번 위치에 있는 햄버거
• 10번 위치에 있는 사람: 8번 위치에 있는 햄버거
• 12번 위치에 있는 사람: 11번 위치에 있는 햄버거

식탁의 길이 N, 햄버거를 선택할 수 있는 거리 K, 사람과 햄버거의 위치가 주어졌을 때, 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

제한

•  1≤𝑁≤20,000
•  1≤𝐾≤10

예제 입력 1 복사

20 1
HHPHPPHHPPHPPPHPHPHP

예제 출력 1 복사

8

예제 입력 2 복사

20 2
HHHHHPPPPPHPHPHPHHHP

예제 출력 2 복사

7

출처