프로그램 명: wat_dinner
제한시간: 1 초
CCC에 출전 학생들이 저녁 식사를 하기 위해 줄을 서고 있습니다.
N (1 <= N <= 100)명의 학생들은 식당 입구에서 일자로 줄을 지어 기다리고 있습니다.
CCC를 주최하는 닥터 V는 저녁 식사가 시작하기 직전에 학생들이 서로 다른 프로그램 언어를 사용하는 사람들 옆에 서있는 것을 정말 싫어한다는 걸 눈치챘습니다. 다행히도 CCC에는 Gnold와 Helpfile라는 두 언어만 사용할 수 있습니다. 그리고 학생들은 적어도 K (1 <= K <= 6) 명 이상의 같은 언어를 사용하는 다른 학생들과 모여 함께 식사를 하기로 결정하기도 했습니다.
닥터 V는 다음과 같은 방법으로 학생들을 들여보내기로 했습니다.
- 연속으로 줄지어 서있는 K명 이상의 같은 언어를 사용하는 학생들의 그룹을 지어 식당으로 보냅니다.
- 남은 학생들은 빠진 학생들의 공간을 매꿉니다. 여기서 같은 언어를 사용하는 학생들이 연속으로 줄지어 서게 될 가능성이 있습니다.
닥터 V는 누가 무슨 언어를 사용하는지를 조사했습니다. 이제 모든 학생이 식당으로 들어갈 수 있는지를 결정해야합니다. 그렇다면 최소 몇 개의 그룹을 지어 식당으로 보내야하는지 출력하는 프로그램을 작성하세요.
입력
-
첫 줄에 N과 K가 입력됩니다.
-
두 번째 줄에는 학생들이 줄을 선 모습이 길의 N의 G 혹은 H로 이루어진 문자열이 주어집니다. (H는 Helpfile를 사용하는, G는 Gnold를 사용하는 학생입니다.)
출력
한 줄에 최소 몇 개의 그룹을 지어 식당으로 보내야하는지를 출력하세요. 모든 학생이 식당으로 갈 수 없다면 -1을 출력하세요.
입출력 예
입력
7 2
GHHGHHG
출력
3
입출력 설명
입력
앞에서부터 한 명의 Gnold 사용자, 두 명의 Helpfile 사용자, 한 명의 Gnold 사용자, 두 명의 Helpfile 사용자, 한 명의 Gnold 사용자가 줄에 서있습니다. 그리고 그룹은 적어도 2명 이상이어야 합니다.
출력
앞의 두 H를 식당으로 보내면 GGHHG 가 되고 다시 H 두 명을 보내면 GGG가 되고, 마지막으로 3명의 G를 보내면 세 그룹으로 모두 식당으로 들어갈 수 있습니다.
출처: 2009 CCC Stage 2
번역+추천:ladown21
[질/답]
[제출 현황]
[푼 후(0)]