백준 14465 : 소가 길을 건너간 이유

• 초기 코드 - 테케만 되고 나머진 실패

처음엔 슬라이딩 윈도우를 생각하지 못해서 정상 신호등 - 0, 고장난 신호등 - 1, 고친 신호등 - 2로 두고

투포인터 개념으로 문제를 풀어보려고 했지만 k개가 유지되지 않아서 틀린 것 같다

	for (int i = 1; i <= n; i++){
            while (rt <= n && cnt <= k){
                if (cnt == k) break;

                if (arr[rt] == 1){
                    arr[rt] = 2; //rt가 2면 1인걸 바꾼것
                    tmp++; // 수리한 신호등 갯수
                }
                cnt++; //현재 이어진 신호등 갯수
                rt++;
            }

            if (cnt >= k) ans = Math.min(ans, tmp);
            if (arr[i] == 2) tmp--; // 수리한 신호등 갯수를 lt가 증가하면서 빼줌
            cnt--;
        }

        System.out.println(ans);

 

슬라이딩 윈도우로 변경하고 바로 풀렸다

딱 보고 문제 유형을 알 수 있을때까지 많이 풀어봐야겠다..

import java.util.*;
import java.io.*;


class Main
{
    public static void main (String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); // 횡단보도 n개
        int k = in.nextInt(); // 연속한 신호등
        int b = in.nextInt(); // 고장난 신호등 갯수

        int[] arr = new int[n+1];
        for (int i = 0 ; i < b; i++){
            int tmp = in.nextInt();
            arr[tmp] = 1;
        }

        int cnt = 0; // 고친 신호등 갯수
        int ans = Integer.MAX_VALUE;

        //처음 k개로 슬라이딩 윈도우
        for (int i = 1; i <= k; i++){
            if (arr[i] == 1) {
                cnt++;
            }
        }

        ans = Math.min(ans, cnt);


        for (int i = k+1; i <= n; i++){
            if (arr[i] == 1) cnt++;
            if (arr[i-k] == 1) cnt--;

            ans = Math.min(ans,cnt);
        }

        System.out.println(ans);
    }
}