흙길 보수하기
시간 제한2초메모리 제한128 MB
겹치지 않는 물웅덩이 구간들과 고정 길이 판자가 주어질 때, 모든 웅덩이를 덮는 데 필요한 최소 판자 수를 구합니다.
문제
어젯밤 내린 큰비로 겨울 캠프장에서 본관까지 이어지는 흙길에 N개의 물웅덩이가 생겼다. 물웅덩이를 모두 덮을 수 있도록 길이가 L인 널빤지가 충분히 준비되어 있다. 각 물웅덩이의 시작 위치와 끝 위치가 주어질 때, 모든 물웅덩이를 덮는 데 필요한 널빤지의 최소 개수를 구하라.
입력
첫째 줄에 두 정수 N과 L이 주어진다.
둘째 줄부터 N개의 줄에는 각 물웅덩이의 정보가 한 줄에 하나씩 주어진다. 각 정보는 물웅덩이의 시작 위치와 끝 위치로 이루어진다. 물웅덩이는 시작 위치 이상, 끝 위치 미만인 구간으로 본다. 각 위치는 0 이상 1,000,000,000 이하의 정수이다. 입력으로 주어지는 물웅덩이들은 서로 겹치지 않는다.
출력
모든 물웅덩이를 덮기 위해 필요한 널빤지의 최소 개수를 출력한다.
힌트
아래와 같이 배치하면 길이가 3인 널빤지가 5개 필요하다.
111222..333444555.... // 길이 3인 널빤지
.MMMMM..MMMM.MMMM.... // 물웅덩이
012345678901234567890 // 좌표