c언어 14465번 소가 길을 건넌 이유 5 (백준)

#include <stdio.h>

int main(void)
{
	int n, k, b;
	scanf("%d %d %d",&n,&k,&b);
	
	char arr[100001]={};
	int sum = 0, min = 0;
	
	while(b--) {
		int tmp;
		scanf("%d",&tmp);
		arr[tmp]=1;
	}
	
	for(int i=1; i<=k; i++) sum += arr[i];
	min = sum;
	for(int i=k+1; i<=n; i++) {
		sum -= arr[i-k];
		sum += arr[i];
		if(min > sum) min = sum;
	} printf("%d", min);
}

 

풀이 : 슬라이드 윈도우

 

슬라이드 윈도우로 앞을 제거하고 뒤를 붙이는 형식으로 b만큼 구역에서 얼마나 가로등이 깨졌는지를 확인 할 수 있습니다 이 중 최솟값을 구하면 됩니다.

 

누적합으로도 풀 수 가 있습니다.

 

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

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