[BOJ 1911] 흙길 보수하기

문제 링크 : https://www.acmicpc.net/problem/1911

문제

어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N(1 ≤ N ≤ 10,000)개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이가 L(1 ≤ L ≤ 1,000,000)인 널빤지들을 충분히 가지고 있어서, 이들로 다리를 만들어 물웅덩이들을 모두 덮으려고 한다. 물웅덩이들의 위치와 크기에 대한 정보가 주어질 때, 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 구하여라.

입력

첫째 줄에 두 정수 N과 L이 들어온다.

둘째 줄부터 N+1번째 줄까지 총 N개의 줄에 각각의 웅덩이들의 정보가 주어진다. 웅덩이의 정보는 웅덩이의 시작 위치와 끝 위치로 이루어진다. 각 위치는 0 이상 1,000,000,000 이하의 정수이다. 입력으로 주어지는 웅덩이는 겹치지 않는다.

출력

첫째 줄에 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 출력한다.

제한

시간 제한	메모리 제한
2sec	128MB

힌트

아래와 같이 5개의 널빤지가 필요하다.

111222..333444555.... // 길이 3인 널빤지

.MMMMM..MMMM.MMMM.... // 웅덩이

012345678901234567890 // 좌표

---

풀이

문제가 참 간단하다. 널빤지로 모든 웅덩이를 덮어야한다. 그럼 하나하나 덮으면 되지 않을까?

문제에서 주어지는 입력으로는 웅덩이는 겹치지 않는다고 한다. 즉, 웅덩이의 좌표에 따라 정렬하여 앞에서부터 덮어나가면 쉽게 해결할 수 있다. 현재 위치를 $cur$이라고 하고, 널빤지의 길이가 $L$이었으므로, 이 위치에 널빤지를 덮게 되면 덮이는 범위는 $[cur, cur + L)$까지가 될 것이다. 그럼 다음 웅덩이를 고려해야하는데, 그 위치가 $cur + L$보다 적은 위치라면 이미 덮인 웅덩이이므로 고려할 필요가 없다. 이외에는 다시 덮어나가면 된다.

그럼 처음 널빤지를 덮는 시작 위치는 어떻게 정해야하는가? 답은 간단하게, 웅덩이의 시작지점에서부터 덮어나가면 모든 웅덩이를 덮을 수 있으면서 널빤지 사용 갯수가 최소가 됨이 보장된다. 직관적인 아이디어에 대한 구현만 진행하면 되는 간단한 문제.

소스코드

Github Link : Source Code

참고 알고리즘 : 그리디 알고리즘