최소 와이파이 수

문제

사람들이 살고 있는 위치가 0과 1로 주어질 때,
모든 사람들이 와이파이를 사용할 수 있도록
거리 m 이내를 커버하는 와이파이를 최소 몇 개 설치해야 하는지 구하는 문제.

와이파이는 사람이 없는 위치에도 설치 가능하며,
정수 위치에만 설치할 수 있고,
설치한 위치로부터 거리 m 이내의 사람들을 모두 커버할 수 있다.

전략

가장 왼쪽 집에 사는 사람을 커버하는 가장 오른쪽 위치에 놓는 것이 좋다.

코드

import java.util.Scanner;

public class Main {
    public static final int MAX_N = 100;

    public static int n, m;
    public static int[] arr = new int[MAX_N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 입력
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i = 0; i < n; i++)
            arr[i] = sc.nextInt();

        // 사람이 살고 있는 곳이 나오면
        // 와이파이를 해당 위치로부터 오른쪽으로 m만큼 떨어진 곳에 놓은 뒤,
        // 2m만큼 떨어진 곳에서 시작하여 다시 탐색을 진행합니다.
        int cnt = 0;
        for(int i = 0; i < n; i++) {
            if(arr[i] == 1) {
                cnt++;
                i += 2 * m;
            }
        }

        System.out.print(cnt);
    }
}