[Hacker Rank] Goodland Electricity
문제
문제 해결 전략
우선 문제에 대한 설명을 간략히 하자면 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';
}
Author And Source
이 문제에 관하여([Hacker Rank] Goodland Electricity), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@easttwave/Hacker-Rank-Goodland-Electricity저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)