기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가
이하인 햄버거를 먹을 수 있다.
햄버거 사람 햄버거 사람 햄버거 사람 햄버거 햄버거 사람 사람 햄버거 사람
위의 상태에서
인 경우를 생각해보자. 이 경우 모든 사람은 자신과 인접한 햄버거만 먹을 수 있다. 10번의 위치에 있는 사람은 11번 위치에 있는 햄버거를 먹을 수 있다. 이 경우 다음과 같이 최대 5명의 사람이 햄버거를 먹을 수 있다.
2번 위치에 있는 사람: 1번 위치에 있는 햄버거
4번 위치에 있는 사람: 5번 위치에 있는 햄버거
6번 위치에 있는 사람: 7번 위치에 있는 햄버거
9번 위치에 있는 사람: 8번 위치에 있는 햄버거
10번 위치에 있는 사람: 11번 위치에 있는 햄버거
12번 위치에 있는 사람: 먹을 수 있는 햄버거가 없음
인 경우에는 6명 모두가 햄버거를 먹을 수 있다.
2번 위치에 있는 사람: 1번 위치에 있는 햄버거
4번 위치에 있는 사람: 3번 위치에 있는 햄버거
6번 위치에 있는 사람: 5번 위치에 있는 햄버거
9번 위치에 있는 사람: 7번 위치에 있는 햄버거
10번 위치에 있는 사람: 8번 위치에 있는 햄버거
12번 위치에 있는 사람: 11번 위치에 있는 햄버거
식탁의 길이
, 햄버거를 선택할 수 있는 거리
, 사람과 햄버거의 위치가 주어졌을 때, 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.
첫 줄에 두 정수 과 가 있다. 그리고 다음 줄에 사람과 햄버거의 위치가 문자 P(사람)와 H(햄버거)로 이루어지는 길이 인 문자열로 주어진다.
첫 줄에 햄버거를 먹을 수 있는 최대 사람 수를 나타낸다.
구현
문자열의 제한 (0,N)을 넘지 않는 선에서, 먹을 수 있는 햄버거의 범위를 지정한다.
범위 중, 가장 왼쪽에 있는 버거를 먹는다면, 최대한 많은 사람이 버거를 먹을 수 있다.
import sys
input = sys.stdin.readline
N,K = map(int,input().split())
line = list(input())
cnt = 0
for i in range(len(line)):
if line[i] =='P':
left = max(i-K,0)
right = min((i+K+1),N)
for j in range(left,right):
if line[j] == 'H':
line[j] = 'X'
cnt+=1
break
print(cnt)
최초엔, 문자열의 제한을 넘지 않는 선에서, distance를 리스트로 구성하는 식으로 접근했다. 예를 들어 K = 2 라면, [2,1] 이라는 리스트를 정의한 후 접근하는 방식으로 했는데, 복잡했고 좀 단순하게 생각해서 제대로 구현하지 못했다.