백준) 1911 흙길 보수하기

1911 흙길 보수하기

문제

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

입력

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

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

출력

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

예제 입력 

3 3
1 6
13 17
8 12

예제 출력 

5

1. 접근

당연히 처음부터 덮으면 된다!

그리디 알고리즘.

2. 풀이

매우 직관적으로 떠오르는 생각이 정답이다.

탐욕적 방법 : 맨 앞의 웅덩이의 처음부터 널빤지를 덮기로 하자.

다 덮고 나면 앞에서 덮은 널빤지가 바로 뒤의 웅덩이에 닿거나 닿지 않는 두 가지 케이스가 발생한다.

닿는다면 남은 웅덩이부분의 처음부터 다시 덮는 부분문제로 귀결되고, 닿지 않는다면 첫 웅덩이를 덮는 부분문제와 완전 동일하다.

따라서 정당성도 증명되었다.

3. 코드

#include <stdio.h>
#include <algorithm>
using namespace std;
 
typedef pair<int, int> p;
bool cmp(const p& p1, const p& p2) {
    if (p1.first == p2.first)
        return p1.second > p2.second;
    else
        return p1.first < p2.first;
}
p pp[10001];
int n, l, i;
 
int main() {
    scanf("%d %d", &n, &l);
    for (i = 0; i < n; ++i)
        scanf("%d %d", &pp[i].first, &pp[i].second);
 
    sort(pp, pp + n, cmp);
    int last = 0, cnt = 0, tmp = 0;
    for (i = 0; i < n; ++i) {
        if (pp[i].second - 1 < last)
            continue;
        if (pp[i].first > last) {
            tmp = (pp[i].second - pp[i].first) / l;
            if ((pp[i].second - pp[i].first) % l != 0)
                tmp++;
            cnt += tmp;
            last = pp[i].first + l * tmp - 1;
        }
        else {
            tmp = (pp[i].second - last - 1) / l;
            if ((pp[i].second - last - 1) % l != 0)
                tmp++;
            cnt += tmp;
            last = last + l * tmp;
        }
    }
    printf("%d", cnt);
    return 0;
}

4. 후기

처음엔 웅덩이들이 당연히 곂치지 않겠거니 하고 매우 간단하게 짰지만,

여러번 틀리는 것으로 보아 테스트케이스에 겹치는 웅덩이들도 있는 모양이다.