(Python) - BOJ(19941번) : 햄버거 분배

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

19941번: 햄버거 분배

---

• 문제 : 

기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 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, 사람과 햄버거의 위치가 주어졌을 때, 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.

 

 

 

 

---

• 풀이 :

각 사람은 자신의 왼쪽에 햄버거가 있는지 찾고 있다면 이를 선택하여 최댓값을 구하면 된다.

 

 

 

---

• 소스코드 : 

 

import sys
input = sys.stdin.readline
 
if __name__ == "__main__":
    N,K = map(int,input().split())
    st = input().strip()
    ans = [0]*N
    cnt = 0
    for idx,key in enumerate(st):
        if key == "H":
            ans[idx] = 1
    if N<=K:
        print(min(list(st).count('H'),list(st).count("P")))
    else:
        for idx,key in enumerate(st):
            if key == 'P':
                if idx > N-K-1:
                    for i in range(idx-K,len(st),1):
                        if ans[i] == 1:
                            ans[i] = 0
                            cnt += 1
                            break
                elif idx >= K:
                    for i in range(idx-K,idx+K+1,1):
                        if ans[i] == 1:
                            ans[i] = 0
                            cnt += 1
                            break
                elif idx < K:
                    for i in range(0,idx+K+1,1):
                        if ans[i] == 1:
                            ans[i] = 0
                            cnt += 1
                            break
        print(cnt)