문제 풀이

문제에서 연속한 K의 신호등이 존재하길 원하므로 연속한 6개를 확인하면 된다
대신, 처음부터 6개의 신호등을 확인해서 몇개의 신호등이 고장났는지 확인해주고, 이 구간을 창문 밀듯이 오른쪽으로 밀어주면서 왼쪽끝지점 오른쪽 끝지점을 확인해주면서 수리할 신호등의 개수를 더하거나 빼준다.
만약 왼쪽 끝에있던 신호등이 고장난 신호등인데 구간에서 벗어났다면 출력할 답에서 -1 해주고

if(arr[l]== 1)
	cnt--;

구간의 오른쪽 끝 + 1에 있는 신호등이 고장난 신호등이라면 구간을 오른쪽으로 밀면서 구간에 합류하게 되기때문에 출력할 답에서 +1 해준다.

 if(arr[l+k] == 1)
	cnt++;

문제 링크

boj/14465

소스코드

PS/14465.java

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;


public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int []arr= new int[100005];
    public static void main(String[] args) throws IOException {
       int n,k,b;
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
        for(int i=0;i<b;i++)
        {
            int a = Integer.parseInt(br.readLine());
            arr[a] = 1;
        }
        int cnt =0;
        for(int i=1;i<=k;i++)
        {
            if(arr[i] ==1)
                cnt++;
        }
        int m = cnt;
        for(int l=1;l+k-1<n;l++)
        {
            if(arr[l]== 1)
                cnt--;
            if(arr[l+k] == 1)
                cnt++;
            m = Math.min(m,cnt);
        }
        bw.write(Integer.toString(m));
        bw.flush();
    }
}