[C++] 백준 14465번: 소가 길을 건너간 이유 5

문제 링크

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

문제 요약

N개의 연속된 횡단보도가 있고, 각 횡단보도에는 신호등이 있다. 이때 B개의 신호등이 쓰러졌을 때, 연속한 K개의 신호등이 존재하기 위해 수리해야하는 신호등의 수를 구해야 한다.

접근 방법

쉬운 누적 합 문제였습니다.

신호등이 존재하면 1, 존재하지 않으면 0으로 배열을 초기화합니다. 그리고 누적합을 구해둡니다.

이제, 길이가 K인 모든 구간합의 최댓값을 구하고, K에서 최댓값을 뺀 결과를 출력해주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

int arr[100001];

int main(void)
{
	int n, k, b;
	cin >> n >> k >> b;

	fill_n(arr, 100001, 1);

	for (int i = 0; i < b; i++)
	{
		int num;
		cin >> num;
		arr[num]--;
	}

	for (int i = 2; i <= n; i++)
		arr[i] += arr[i - 1];

	int m = 0;
	for (int i = k; i <= n; i++)
		m = max(m, arr[i] - arr[i - k]);

	cout << k - m;
	return 0;
}