[Codeforces 1066B] Heaters

[Codeforces 1066B] Heaters

역시나 전형적인 그리디 문제이다. 처음에 풀 때는 문제 조건을 잘못 이해해서 한참 고생했다. '1'은 히터가 존재하는 위치일 뿐 전원은 꺼져있다고 간주해야하는데 나는 전원이 켜져있다고 생각해서 실제 정답보다 답을 적게 구했다.

풀이는 간단하다. 왼쪽에서부터 오른쪽으로 가면서 현재 위치(cur)에서 가장 오른쪽에 있는 히터를 발견하면, 그 지점(i)을 기준으로 [i-r+1,i+r-1]은 heating할 수 있다는 의미이다. 그래서 나는 그 히터의 범위가 닿지 않기 시작하는 위치(=i+r)로 cur를 바꿔주면 된다.

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stdlib.h>
#include<stack>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
/****************************Default Template******************************/
#define SIZE 1009
// #define IMP
// #define INF
// const int MOD=
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int> pq;
priority_queue<int,vector<int>,greater<int>> mpq;
map<int,int> mp;
stack<int> st;
set<int> set_i;
/****************************Default Template******************************/
 
 
 
int heat[SIZE];
int main(){
    int n,r;    scanf("%d %d",&n,&r);
 
    for(int i=1 ; i<=n ; i++)
        scanf("%d",&heat[i]);
 
    int ans=0,cur=1;
 
    while(cur<=n){
        int check=0;
 
        for(int i=min(n,cur+r-1) ; i>=max(1,cur-r+1) ; i--){
            if(heat[i]){
                ans++;
                check=1;
                cur=i+r;
                break;
            }
        }
    
        if(!check){
            printf("-1\n");
            return 0;
        }
    }
 
    printf("%d\n",ans);
    return 0;
}