BOJ14465 소가 길을 건너간 이유 5

https://www.acmicpc.net/problem/14465

14465번: 소가 길을 건너간 이유 5

이문제는 투포인터( 슬라이딩 윈도우) 또는 누적합을 이용하여 풀 수 있다.

 

 

슬라이딩 윈도우 방식

import java.util.*;
import java.io.*;
public class Main
{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] input1 = br.readLine().split(" ");
        int n = Integer.parseInt(input1[0]);
        int k = Integer.parseInt(input1[1]);
        int b = Integer.parseInt(input1[2]);
        boolean[] signal = new boolean[n+1];
        Arrays.fill(signal, true);
        for(int i=0 ; i<b; i++){
            signal[Integer.parseInt(br.readLine())] = false;
        }
        
        
        
        int count=0;
        for(int left =1;left<k+1;left++){
            count+= signal[left]? 1:0;
            
        }
        int max = count;
        for(int left =2; left<n-k+2; left++){
            if(signal[left-1]) count--;
            if(signal[left-1+k]) count++;
            max = Math.max(max,count);
        }
        
        
        System.out.println(k-max);
	}
}

 

 

누적합 방식

 

import java.util.Scanner;

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

        int N = sc.nextInt();
        int K = sc.nextInt();
        int B = sc.nextInt();
        boolean[] isBroken = new boolean[N + 1];
        while (B-- > 0) {
            int idx = sc.nextInt();
            isBroken[idx] = true;
        }

        int[] accBroken = new int[N + 1];
        for (int i = 1; i <= N; i++)
            accBroken[i] = accBroken[i - 1] + (isBroken[i] ? 1 : 0);

        int ans = K;
        for (int i = 1; i <= N - K + 1; i++)
            ans = Math.min(ans, accBroken[i + K - 1] - accBroken[i - 1]);
        System.out.println(ans);
    }
}