시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 78 | 21 | 14 | 22.951% |
오케스트라에서 연주자는 쉬는 시간 동안 악보를 넘긴다.
문제에서 모든 음표와 쉼표의 음길이는 $1$초라고 가정한다. 연주자는 쉼표일 때 쉴 수 있고 한 번에 쉬는 시간이 $K$초 이상은 되어야 악보를 넘길 수 있다. 즉, 악보의 마지막 장을 제외한 모든 장의 끝에는 $K$개의 쉼표가 연속해서 있어야 한다. 또한, 악보 한 장에는 음표와 쉼표를 합하여 최대 $X$개 적을 수 있다.
이 조건을 만족하면서 모든 기호를 순서대로 기록하기 위해 필요한 악보 페이지 수의 최솟값을 구하는 프로그램을 작성하자.
첫 번째 줄에 기호의 개수 $N$, 악보 한 장에 쓸 수 있는 기호의 개수 $X$, 페이지를 넘기기 위해 필요한 쉼표의 개수 $K$가 공백으로 구분되어 주어진다. $(1 \leq K \lt X \lt N \leq 200\,000)$
두 번째 줄에 기호를 나타내는 $N$개의 정수 $A_i$가 공백으로 구분되어 주어진다. $(A_i \in \{0, 1\})$
$A_i=0$이면 쉼표이고, $A_i=1$이면 음표이다.
필요한 악보 페이지 수의 최솟값을 출력한다. 조건을 만족하는 악보를 만들 수 없다면 $-1$을 출력한다.
10 3 1 1 1 0 1 0 0 1 0 1 1
4
7 3 2 1 0 0 0 1 0 1
-1
실제로 악보를 작성하는 방법과는 다를 수 있다.
Contest > SW마에스트로 > 제13기 알고리즘 대회 E번