문제 1022 · 기초 4
골목 가로등
그리디 · 정렬
테스트별 제한 1500ms · 브라우저 채점
문제
일직선으로 뻗은 골목에 집 N채가 있다. 집의 위치는 골목 입구에서 잰 거리(미터, 정수)로 주어지고, 여러 집이 같은 위치에 있을 수도 있다. 가로등은 정수 위치 어디에나 세울 수 있고, 위치 p 에 세운 가로등은 p − D 이상 p + D 이하의 구간을 밝힌다. 모든 집을 밝히려면 가로등이 최소 몇 개 필요한지 구하라.
입력
첫째 줄에 집의 수 N 과 D 가 주어진다. (1 ≤ N ≤ 30,000, 0 ≤ D ≤ 1,000,000) 둘째 줄에 집의 위치 N개가 주어진다. 위치는 0 이상 1,000,000 이하의 정수이고 정렬되어 있지 않다.
출력
필요한 가로등의 최소 개수를 출력한다.
예제 입력 1
5 2 1 9 3 5 12
예제 출력 1
2
예제 입력 2
3 0 7 7 8
예제 출력 2
2
힌트 펼치기
- 아직 밝혀지지 않은 집 중 가장 왼쪽 집을 생각하자. 그 집을 밝히는 가로등은 되도록 오른쪽, 즉 그 집 + D 에 세우는 것이 손해가 없다.
- 그 가로등은 집 + 2D 까지 밝힌다. 그보다 오른쪽에 있는 첫 집에서 같은 일을 되풀이한다.
관련 장
풀이 작성
코드는 서버로 전송하지 않습니다. 테스트가 공개되는 연습용 채점으로, 대회·인증용이 아닙니다.
풀이를 제출하면 여기에서 결과를 확인할 수 있습니다.
로그인 여부와 관계없이 이 브라우저에만 최근 제출 50개를 저장합니다.