가로등
면접 대비시간 제한1초메모리 제한64 MB
각각 좌우로 K미터를 비추는 가로등들이 있을 때, 1번부터 N번까지 모든 미터를 밝히기 위해 추가로 필요한 가로등의 최소 개수를 구한다.
문제
대림절이 되었다. 길이가 미터인 거리에 가로등 개가 서 있다. 거리의 각 미터에는 1번부터 번까지 번호가 붙어 있다. 가로등은 자신이 놓인 미터와 그 좌우로 미터씩을 밝힌다. 즉 번 미터에 놓인 가로등은 번부터 번까지를 모두 밝힌다. 한 미터를 여러 가로등이 함께 밝혀도 상관없다. 가로등의 위치는 모두 다르다.
지금 서 있는 가로등만으로는 거리 미터가 전부 밝지 않을 수 있다. 거리 전체가 밝아지도록 1번과 번 사이의 위치에 가로등을 더 세우려고 한다. 추가로 필요한 가로등의 최소 개수를 구하여라.
입력
첫째 줄에 이 주어진다. ()
둘째 줄에 이 주어진다. ()
셋째 줄에 가 주어진다. ()
이어지는 개의 줄에 가로등의 위치가 한 줄에 하나씩 오름차순으로 주어진다. 위치는 서로 다르고 모두 1 이상 이하이다.
출력
추가로 세워야 하는 가로등의 최소 개수를 출력한다.
힌트
첫 번째 예제에서는 미터가 이미 모두 밝으므로 가로등을 더 세우지 않아도 된다.
세 번째 예제에서는 가로등 하나를 더 세워야 한다. 예를 들어 13번 미터에 세우면 된다.