만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

가로등

면접 대비

시간 제한1초메모리 제한64 MB

요약
각각 좌우로 K미터를 비추는 가로등들이 있을 때, 1번부터 N번까지 모든 미터를 밝히기 위해 추가로 필요한 가로등의 최소 개수를 구한다.
난이도

보통10점 중 4점

유형
그리디, 정렬, 구간, 구현
정답자
아직 제출이 없습니다

문제

대림절이 되었다. 길이가 NN미터인 거리에 가로등 MM개가 서 있다. 거리의 각 미터에는 1번부터 NN번까지 번호가 붙어 있다. 가로등은 자신이 놓인 미터와 그 좌우로 KK미터씩을 밝힌다. 즉 XX번 미터에 놓인 가로등은 X−KX - K번부터 X+KX + K번까지를 모두 밝힌다. 한 미터를 여러 가로등이 함께 밝혀도 상관없다. 가로등의 위치는 모두 다르다.

지금 서 있는 가로등만으로는 거리 NN미터가 전부 밝지 않을 수 있다. 거리 전체가 밝아지도록 1번과 NN번 사이의 위치에 가로등을 더 세우려고 한다. 추가로 필요한 가로등의 최소 개수를 구하여라.

입력

첫째 줄에 NN이 주어진다. (1≤N≤10001 \le N \le 1000)

둘째 줄에 MM이 주어진다. (1≤M≤N1 \le M \le N)

셋째 줄에 KK가 주어진다. (0≤K≤N0 \le K \le N)

이어지는 MM개의 줄에 가로등의 위치가 한 줄에 하나씩 오름차순으로 주어진다. 위치는 서로 다르고 모두 1 이상 NN 이하이다.

출력

추가로 세워야 하는 가로등의 최소 개수를 출력한다.

힌트

첫 번째 예제에서는 NN미터가 이미 모두 밝으므로 가로등을 더 세우지 않아도 된다.

세 번째 예제에서는 가로등 하나를 더 세워야 한다. 예를 들어 13번 미터에 세우면 된다.

예제3

  1. 예제 1

    입력
    5
    2
    2
    1
    5
    
    예상 출력
    0
    
  2. 예제 2

    입력
    26
    3
    3
    3
    19
    26
    
    예상 출력
    2
    
  3. 예제 3

    입력
    13
    2
    10
    1
    2
    
    예상 출력
    1