백준 19941(햄버거 분배 ) - Python(파이썬) - 그리디

19941번: 햄버거 분배

예제 설명

20 1
HHPHPPHHPPHPPPHPHPHP

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
H	H	P	H	P	P	H	H	P	P	H	P	P	P	H	P	H	P	H	P

  1. 2번의 사람 -> 1번 or 3번의 햄버거를 먹을 수 있지만 무조건 앞에 남은 햄버거 먹기 -> visted[1] =T 

visted ( 먹었는지 안 먹었는지 알려주는 배열 )
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
F	T	F	F	F	F	F	F	F	F	F	F	F	F	F	F	F	F	F	F

 2. 4번의 사람 -> 3번의 햄버거 먹음 -> visted[3] = T

visted ( 먹었는지 안 먹었는지 알려주는 배열 )
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
F	T	F	T	F	F	F	F	F	F	F	F	F	F	F	F	F	F	F	F

3. 5번의 사람 -> 6번의 햄버거 먹음 -> visted[6]=T

visted ( 먹었는지 안 먹었는지 알려주는 배열 )
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
F	T	F	T	F	F	T	F	F	F	F	F	F	F	F	F	F	F	F	F

4. 8번의 사람 -> 7번의 햄버거 먹음 -> visted[7] =T

visted ( 먹었는지 안 먹었는지 알려주는 배열 )
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
F	T	F	T	F	F	T	T	F	F	F	F	F	F	F	F	F	F	F	F

5. 9번의 사람 -> 10번의 햄버거 먹음 -> visted[10]=T

visted ( 먹었는지 안 먹었는지 알려주는 배열 )
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
F	T	F	T	F	F	T	T	F	F	T	F	F	F	F	F	F	F	F	F

6. 13번의 사람 -> 14번 햄버거 먹음 -> visted[14]=T

visted ( 먹었는지 안 먹었는지 알려주는 배열 )
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
F	T	F	T	F	F	T	T	F	F	T	F	F	F	T	F	F	F	F	F

7. 15번의 사람 -> 16번의 햄버거 먹음 -> visted[16]=T

visted ( 먹었는지 안 먹었는지 알려주는 배열 )
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
F	T	F	T	F	F	T	T	F	F	T	F	F	F	T	F	T	F	F	F

8. 17번의 사람 -> 18번의 햄버거 먹음 -> visted[17]=T

visted ( 먹었는지 안 먹었는지 알려주는 배열 )
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
F	T	F	T	F	F	T	T	F	F	T	F	F	F	T	F	T	F	T	F

따라서 총 먹은 햄버거의 개수는 T의 개수로 8개이다.

visted ( 먹었는지 안 먹었는지 알려주는 배열 )
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
F	T	F	T	F	F	T	T	F	F	T	F	F	F	T	F	T	F	T	F

문제 해설
① n(식탁의 길이),k(햄버거를 선택할 수 있는 거리), array(사람과 햄버거의 위치 입력받는 함수) 받아들이기 ,visted(햄버거를 먹었는지 안 먹었는지 알려주는 배열 ) 선언
② 사람(P)일 경우 사람의 위치- k, 사람의 위치+k까지 for루프 돌리기
③ 루프 돌릴 때 사람의 위치 -k, 사람의 위치+k의 값이 0과 n 사이의 경우 햄버거를 안 먹었을 경우 visted의 값을 True로 변경하면서 count값을 1씩 더하기

Python(파이썬) 

import sys
#식탁의 길이,햄버거를 선택할 수 있는 거리 입력받기
n,k = map(int,sys.stdin.readline().split())
#햄버거와 사람의 위치 그래프
array = sys.stdin.readline()
#햄버거를 먹었는지 안 먹었는지 배열
visted=[False]*n
#햄버거 먹을 수 있는 최대 사람 수
count=0
for i in range(n):
	#사람의 경우
    if array[i]=='P':
    	#i에서 K까지의 거리에 있는 햄버거의 경우
        for j in range(i-k,i+k+1):
        	#인덱스 안에 있게
            if j>=0 and j<n:
            	#햄버거를 안 먹었을 경우
                if not visted[j] and array[j]=='H':
                	#햄버거를 먹었다고 표시
                    visted[j]=True
                    #햄버거를 먹을 수 있는 사람수 +1
                    count+=1
                    break

print(count)

import sys
#식탁의 길이,햄버거를 선택할 수 있는 거리 입력받기
n,k = map(int,sys.stdin.readline().split())
#햄버거와 사람의 위치 그래프
array = sys.stdin.readline()
#햄버거를 먹었는지 안 먹었는지 배열
#False말고 F라고 초기화
visted=['F']*n
for i in range(n):
	#사람의 경우
    if array[i]=='P':
    	#i에서 K까지의 거리에 있는 햄버거의 경우
        for j in range(i-k,i+k+1):
        	#인덱스 안에 있게
            if j>=0 and j<n:
            	#햄버거를 안 먹었을 경우
                if visted[j]=='F' and array[j]=='H':
                	#햄버거를 먹었다고 표시
                    visted[j]='T'
                    break

print(visted.count('T'))