수도관 누수 수리
면접 대비시간 제한2초메모리 제한128 MB
누수 위치들과 고정된 테이프 길이가 주어질 때, 각 누수를 양쪽으로 0.5 이상 덮도록 필요한 최소 테이프 개수를 구합니다.
문제
여러 지점에서 물이 새는 수도관이 있다. 누수 지점은 수도관의 왼쪽 끝에서 정수 거리만큼 떨어진 위치로 주어진다.
길이가 L인 테이프를 원하는 만큼 사용할 수 있다. 한 누수 지점을 막으려면 그 지점의 왼쪽과 오른쪽을 각각 0.5 이상 덮어야 한다. 테이프는 자를 수 없지만, 서로 겹쳐 붙일 수 있다.
누수 지점들의 위치와 테이프 길이 L이 주어질 때, 모든 누수를 막는 데 필요한 테이프의 최소 개수를 구하라.
입력
첫째 줄에 누수 지점의 개수 N과 테이프 길이 L이 주어진다. 둘째 줄에 누수 지점의 위치 N개가 주어진다.
N과 L은 1 이상 1,000 이하의 정수이며, 각 위치는 1 이상 1,000 이하의 정수이다.
출력
첫째 줄에 필요한 테이프의 최소 개수를 출력한다.