KOI 1차 2020 중1/고2- 햄버거 분배 > 문제은행 : 정보올림피아드&알고리즘




4520 : 햄버거 분배

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
68 회   
시도횟수
203 회   

문제

기다란 벤치 모양의 식탁에 사람들과 햄버거가​ 아래 그림과 같이 단위 간격으로 놓여 있다.

사람들은 자신의 위치에서 거리가 k 이하인 햄버거를 먹을 수 있다. 왼쪽 오른쪽은 상관없다.


 

위 그림에서 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, 그리고 사람과 햄버거의 위치가 주어졌을 때 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.

 


입력형식

입력의 첫 줄에는 두 정수 N과 k가 나온다. (1≤N≤​20,000, 1≤​k≤​10) 그리고 다음 줄에 사람과 햄버거의 위치가 문자 P(사람)와 H(햄버거)로 이루어지는 길이 N인 문자열로 주어진다.


출력형식

여러분은 첫 줄에 하나의 정수를 출력한다.

이 수는 입력에 대해서 햄버거를 먹을 수 있는 최대 사람 수를 나타낸다.

 

 

추가 제약 조건

 

20점 상당의 테스트 케이스는 N≤​20이다.

20점 상당의 테스트 케이스는 N≤​2,000이다.

60점 상당의 테스트 케이스는 추가적인 제약 조건이 없다.


입력 예

20 1
HHPHPPHHPPHPPPHPHPHP

출력 예

8

입력 예

20 2
HHHHHPPPPPHPHPHPHHHP

출력 예

7

데이타 만든사람 : ohjtgood

Greedy

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP