소가 길을 건너간 이유 5

면접 대비

시간 제한2초메모리 제한512 MB

요약

N개의 신호등 중 B개가 고장 난 위치가 주어질 때, 연속한 K개가 모두 작동하도록 고쳐야 하는 최소 개수를 구한다.

난이도: 쉬움10점 중 3점
유형: 슬라이딩 윈도우, 배열, 누적 합, 완전 탐색
정답자: 아직 제출이 없습니다

문제

농부 존의 농장에는 원형 길이 있다고 했지만, 길은 그것만 있는 게 아니다. 그 옆에는 일자형 길이 있고, 이 길에는 1번부터 $N$ 번까지 번호가 붙은 횡단보도 $N$ 개( $1 \le N \le 100{,}000$ )가 있다. 존은 교통사고를 막으려고 모든 횡단보도에 신호등을 설치해 두었다.

그러던 어느 날 강한 뇌우가 몰아쳐 신호등 몇 개가 고장 났다. 존은 정상적으로 작동하는 신호등이 연속으로 $K$ 개 이어지도록 신호등을 수리하려고 한다. 이번에도 존을 도와주자.

입력

첫째 줄에 $N$ , $K$ , $B$ ( $1 \le B, K \le N$ )가 주어진다. 다음 $B$ 개의 줄에는 고장 난 신호등의 번호가 한 줄에 하나씩 주어진다.

출력

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

예제1

예제 1
입력
```
10 6 5
2
10
1
5
9
```
예상 출력
```
1
```