[백준 c++] 1911 흙길 보수하기

문제

https://www.acmicpc.net/problem/1911
N개의 물웅덩이를 길이 L짜리 널빤지로 덮으려고할 때 필요한 널빤지의 최소 개수를 구하는 문제다.

풀이

널빤지를 최소로 하려면 웅덩이를 덮고 남은 널빤지를 이어서 사용해야한다.
따라서 pair vector로 입력을 받아 정렬해준다.
이전 사용했던 널빤지가 끝난 위치를 idx로 둔다.
idx < v[i].first : 웅덩이길이 = v[i].second - v[i].first
idx >= v[i].first: 웅덩이 길이 = v[i].second - idx

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, l, ret, idx, cnt;
int main()
{
    cin >> n >> l;
    vector<pair<int, int>> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end());
    for (int i = 0; i < n; i++)
    {
        if (v[i].second <= idx)
            continue;
        if (idx < v[i].first)
        {
            cnt = (v[i].second - v[i].first) / l;
            if ((v[i].second - v[i].first) % l)
                cnt += 1;
            idx = v[i].first + cnt * l;
        }
        else
        {
            cnt = ((v[i].second - idx) / l);
            if ((v[i].second - idx) % l)
                cnt += 1;
            idx = idx + cnt * l;
        }
        ret += cnt;
    }
    cout << ret << "\n";
}