Problems
정올국에는 일직선으로 놓여진 N개의 도시가 있다. 인접한 두 도시간의 거리는 1이다.
국토부 장관인 도훈이는 이 중 몇 개의 도시에 발전소를 지으려고 한다.
도시 지형 문제 때문에, 모든 도시에 발전소를 지을 수 있는 것은 아니다.
발전소를 지으면, 발전소가 건설된 도시와의 거리가 K보다 작은 모든 도시에 전력이 들어온다.
모든 도시에 전력을 공급하기 위한 발전소 수의 최소값을 구하는 프로그램을 작성하라.
Input
첫 줄에 N과 K가 주어진다.
둘째 줄에, N개의 정수가 주어지며, 이는 0 또는 1이다.
0이면 해당 도시에는 발전소를 건설할 수 없다는 뜻이며, 1이면 가능하다는 뜻이다.
입력데이터의 40%에 있어서 1≤K≤N≤1,000을 만족하며, 나머지의 경우 1≤K≤N≤100,000을 만족한다.
Output
모든 도시에 전력을 공급하기 위한 발전소 수의 최소값을 출력한다.
모든 도시에 전력 공급이 불가능한 경우 -1을 출력한다.
Example
6 2
0 1 1 1 1 0
2
Source
Hackerrank
You must sign in to write code.