[Python] 백준 19941 햄버거 분배

 

문제 분석

• 사람들은 자신의 위치에서 거리가 K 이하인 햄버거를 먹을 수 있다.
• n : 식탁의 길이
• k : 햄버거를 선택할 수 있는 거리
• 사람은 좌우로 인접한 k개의 거리 이내에 존재하는 햄버거만 먹을 수 있다.
• 햄버거를 먹을 수 있는 사람의 최대 수

 

풀이

1. 최적해
   • "햄버거를 먹을 수 있는 최대 사람 수"를 어떻게 구할 수 있을까?
   • 왼쪽 사람부터 좌, 우 존재하는 k거리 이내의 햄버거 중 가장 좌측에 있는 것을 먹는 것이 모든 사람이 가장 많은 햄버거를 먹을 수 있는 방법이다.
   • 가장 왼쪽의 것을 먹어야 이후의 선택지가 늘어나기 때문
2. 풀이
   • 사람 p가 발견되면, 좌우 사이의 인접한 k개의 햄버거 탐색
   • 햄버거를 발견하면 cnt + 1
   • 해당 위치는 먹은 햄버거로 표시
   • 즉시 정답으로 사용
3. 시간 복잡도
   • N명에 대해 K개의 인접한 원소를 탐색해야 한다.
   • 따라서 시간 복잡도는 O(n) * O(k)
   • n은 최대 20,000개, k는 최대 200,000개

 

정답 코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
table = list(input().strip())
cnt = 0

for i in range(len(table)) :
    if table[i] == 'P' :
        for j in range(i-k, i+k+1) :
            if j < 0 or j >= n : # 범위 넘으면
                continue
            if table[j] == 'H' :
                table[j] = 'eat'
                cnt += 1
                break
print(cnt)