27893번 - 특별한 드롭킥 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 294 | 60 | 50 | 24.752% |
문제
NLCS Jeju의 구조는 생각보다 부실해서, 벽이나 문 등을 드롭킥으로 부술 수 있다.
NLCS Jeju의 복도는 1차원 수직선으로 모델링할 수 있으며, 동호의 현재 좌표는 $x=0$이다. 동호는 $x=N$에 있는 교실로 가고 싶다. 그러나, NLCS Jeju의 구조는 매우 부실하기에, $1 \le i \le N$인 어떤 정수 $i$에 대해서도 $x=i$에 장애물이 존재할 수 있다.
복도의 구조는 .과 X로 이루어진 길이 $N$의 문자열로 표현할 수 있다. $i$번째 문자는 $x=i$에 대한 장애물의 존재 여부를 의미한다. 문자열의 $i$번째 문자가 X라는 것은, $x=i$에 장애물이 존재함을 의미한다.
동호는 $x=N$에 도착하기 위해 다음과 같은 동작을 $1$번 이상 수행할 수 있다. 다음 두 동작에 대한 설명은 동호가 $x=i$에 있음을 가정하고 설명한다.
- $x=i+1$에 장애물이 없을 시, $x=i+1$로 이동한다. 이 동작에는 $1$의 시간이 소요된다.
- $x=i+1$부터 연속하여 존재하는 장애물을 모두 제거하고, 제거된 장애물 중 가장 $x$좌표가 큰 장애물의 좌표로 이동한다. 이 동작에는 $2$의 시간이 소요된다.
동호가 $x=0$에 있는 동안, 동호는 $1 \le i \le N$이고 $x=i$에 장애물이 존재하지 않는 정수 $i$를 골라서 $x=i$에 장애물을 설치하는 동작을 최대 $M$번 할 수 있다. 이 동작에는 시간이 소요되지 않는다.
복도의 구조가 주어졌을 때, 동호가 $x=N$에 도착하는 데 걸리는 최소 시간을 구하는 프로그램을 작성하여라.
입력
첫째 줄에 $N$과 $M$이 공백을 사이에 두고 주어진다.
둘째 줄에 복도의 구조를 나타내는 길이 $N$의 문자열 $S$가 주어진다. $S$의 $i$번째 문자가 .이면 $x=i$에 아무것도 없음을 뜻하고, X면 장애물이 하나 존재하는 것이다.
출력
첫째 줄에 동호가 $x=N$에 도착하는 데 걸리는 최소 시간을 출력한다.
제한
- $1 \le N \le 200\,000$
- $0 \le M \le N$
- $M$은
.의 개수보다 적거나 같다.
예제 입력 1
4 1 .XX.
예제 출력 1
3
출처
High School > NLCS Jeju > GEC-Cup E번
- 문제를 만든 사람: dhyang24, joonseok_aaren_kang
- 문제를 검수한 사람: dohoon, firstin0907, hjroh0315, jk410, kiwiyou, mjhmjh1104, parkky, sait2000
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호