[백준] 햄버거 분배 : 19941번 - Python

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

19941번: 햄버거 분배

 

 

 

문제를 풀면서 몰랐던 개념

 

반복문에서 변수의 범위를 지정할 때 괄호 안에만 범위를 지정할 수 있는 것이 아니라, 조건문을 사용해서 변수의 범위를 지정해준 후 구현할 수 있다.

 

 

 

문제의 접근 방법

 

- 최대한 많은 사람들이 햄버거를 먹으려면, 마지막 사람이 햄버거를 먹을 경우를 대비해서 최대한 자신에게 인접한 햄버거들 중 제일 왼쪽 햄버거를 먹어야 함.

- 햄버거를 먹었다면 중복되지 않게 먹은 표시를 해주어야 함.

- 반복문 범위 지정에 유의해야 함.

 

 

 

내가 막혔던 부분

 

- 반복문의 범위를 지정하는 방법이 괄호 안에 변수가 돌아갈 크기를 설정해주는 것 밖에 생각을 못했는데, 해당 변수를 조건문에 넣어줘서 그 값 안에 있는 변수라면 해당 반복문이 실행될 수 있게 구현할 수 있다는 것을 알았다. = 이 부분에서 꽤 오랜시간 헤맸다.

- 처음에는 최대한 왼쪽에 있는 햄버거를 먹어야 최대한 많은 사람이 먹을 수 있다는 것을 생각하지 못했다.

 

 

 

문제 풀이 방법

 

(1) 식탁의 길이(N), 햄버거를 선택할 수 있는 거리(K) 입력받기

 

(2) 사람과 햄버거의 위치가 주어져 있는 문자열 s를 입력받아 리스트로 저장하기

 

(3) 식탁의 길이 N만큼 반복하는 반복문을 돌려서 만약 문자열 s의 i번째 요소가 P라면(사람이라면) 그 요소에서 +k, -k 만큼의 범위 안에서 또다른 반복문을 돌려서 햄버거를 찾는다.

이 때, 햄버거를 선택할 수 있는 거리가 k이므로 그만큼 앞뒤로 인접한 범위 내의 햄버거 중 가장 왼쪽에 있는 햄버거를 먹을 수 있도록 해야한다. (여기서 i+k+1인 이유는 반복문의 범위 설정은 '미만'의 개념이기 때문에 +1을 해줌.)

 

(4) 만약 j가 0부터 N미만이고 문자열 s의 j번째 요소가 H라면 count(햄버거를 먹을 수 있는 사람의 최대 수를 저장하는 변수)에 1을 누적해서 더해준다. 더했으면 더 이상 중복해서 햄버거를 먹지 않게 break문을 통해 반복문 탈출!

이 때, j범위를 지정해준 이유는 인덱스의 범위가 리스트의 범위를 초과하기 때문이다.

 

(5) (3) ~ (4) 과정을 반복해서 구해진 최대 사람의 수 count를 출력하기!

 

 

 

소스코드

N,K = map(int, input().split())
s = list(input())

count = 0
for i in range(N):
    if s[i] == 'P':
        for j in range(i-K, i+K+1):
            if 0 <= j < N and s[j] == 'H':
                count += 1
                s[j] = 'X'
                break

print(count)