[C++]/백준 1911번 흙길 보수하기

• 문제

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

• 입력

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

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

• 출력

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

• 예제 입력

3 3
1 6
13 17
8 12

• 예제 출력

5

• 접근방식

1. 널빤지를 어떻게 채울 것인가?
2. 겹치는 부분은 하나로 처리

 

• 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, l, idx, plank, result;
int a, b;
vector<pair<int, int>> v;

int main()
{
    cin >> n >> l;

    for (int i = 0; i < n; i++)
    {
        cin >> a >> b;
        v.push_back({ a,b });
    }

    sort(v.begin(), v.end());

    for (int i = 0; i < n; i++)
    {
        if (v[i].second <= idx)  continue; // 널빤지 끝 부분 index
        if (idx < v[i].first)
        {
            plank = (v[i].second - v[i].first) / l + ((v[i].second - v[i].first) % l ? 1 : 0);
            idx = v[i].first + plank * l;
        }
        else // 웅덩이의 크기가 더 큰 경우
        {
            plank = (v[i].second - idx) / l + ((v[i].second - idx) % l ? 1 : 0);
            idx = idx + plank * l;
        }
        result += plank;
    }

    cout << result;

    return 0;
}

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

1911번: 흙길 보수하기