문제

문제 해결 전략

우선 문제에 대한 설명을 간략히 하자면 k는 전력을 공급할 수 있는 범위라고 생각하면 된다. reachable < k, k보다 작은 distance에 위치한 인덱스에는 전력 공급이 가능하다. 이런 규칙 때문에 탐욕 알고리즘에 의해서 결정할 수 있는데 순차적으로 인덱스 0에서 부터 탐색을 하게 되면
6 2
0 1 1 1 1 0
이런 예시에서
0 1 1 1 1 0
0 1 2 3 4 5
1번 인덱스오 3번 인덱스를 바로 선택하기때문에 인덱스 5번부터 내려오는 방식으로 가는게 나을것 같다는 생각을 했다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int pylons(int k, vector<int> arr){
	int res = 0;
	int i = 0;

	while(i < arr.size()){
		
		bool found = false;	
		for(int l = i+(k-1);(l >= i - k+1) && (l >= 0);l--) {
			if(l < arr.size()){
				if(arr[l] == 1){
					res++;
					i = l+k;
					found = true;		
					break;
				}
			}
		}	
		if(!found) return -1;
	}

	return res;
}

int main(){
	int n, k; cin >> n >> k;

	vector<int> arr(n, 0);

	for(int i = 0;i < n;i++) cin >> arr[i];

	int res = pylons(k, arr);
	cout << res << '\n';
	

}