문제

농부 존의 농장에 원형 길이 있다고 했지만, 길은 그뿐만이 아니다. 그 옆에 일자형 길이 있는데, 1번부터 N번까지의 번호가 붙은 횡단보도 N (1 ≤ N ≤ 100,000)개로 이루어져 있다. 교통사고를 방지하기 위해 존은 각 횡단보도에 신호등을 설치해 놓았다. 그러던 어느 날, 강력한 뇌우로 인해 몇몇 신호등이 망가졌다. 존은 연속한 K개의 신호등이 존재하도록 신호등을 수리하고 싶다. 이번에도 우리가 존을 도와주자.

입력

첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다.

출력

정상적으로 작동하는 연속 K개의 신호등이 존재하려면 최소 몇 개의 신호등을 수리해야 하는지 출력한다.

예제

---

풀이 (완전 탐색)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	ios::sync_with_stdio(0);
    cin.tie(0);

	int n, k, b; // n은 최대 10만
	cin >> n >> k >> b;

	vector<int> broken(b + 1);
	for(int i = 1; i <= b; i++){
		cin >> broken[i]; // 고장난 신호등의 번호 
	}

	vector<pair<int, bool>> v(n + 1);
	for(int i = 1; i <= n; i++){
		v[i].first = i; // 신호등 번호 초기화 

		// 현재 신호등이 고장난 것인지 체크! 
		// i가 broken[j]에 포함된 숫자라면 true 
		for(int j = 1; j <= b; j++){ 
			if(i == broken[j]){ 
				v[i].second = true; // 고장
			}
		} 
		// 그 외의 i는 전부 false 
	}
	
	int fixCount = 0; // 수리해야 할 신호등의 개수 카운팅 
	int ans = 1e9; 
	for(int i = 1; i <= n - k + 1; i++){
		// 연속된 k개의 신호등에 대해서
		// true의 개수 카운팅! 
		for(int j = i; j < i + k; j++){ 
			if(v[j].second == true){ 
				fixCount++; 
			}
		}

		ans = min(ans, fixCount); // 최솟값 갱신 
		fixCount = 0; // 그 다음 구간에 대한 계산을 위해 초기화 필수!!
	}
	
	cout << ans << endl;
	
	return 0;
}