백준 - 1911번 : 흙길 보수하기 (C++)

풀이 방법 : 정렬

물 웅덩이의 시작점을 기준으로 오름차순으로 정렬해준 후 최소 지점부터 널빤지를 덮어나간다고 생각하자.

널빤지가 끝나는 지점의 위치를 기억해두고 만약 다음 물 웅덩이의 시작점이 이전 널빤지가 끝나는 지점보다 더 작은 경우, 해당 위치부터 덮어가기 시작하면 된다.

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

using namespace std;

int main()
{
	int N, L;
	cin >> N >> L;

	vector<pair<int, int>> vecWater(N);

	for (int i = 0; i < N; ++i)
	{
		cin >> vecWater[i].first >> vecWater[i].second;
	}

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

	int Answer = 0;
	int PrevEnd = 0;

	for (int i = 0; i < N; ++i)
	{
		if (PrevEnd >= vecWater[i].second)
			continue;

		int Start = max(vecWater[i].first, PrevEnd);
		int End = vecWater[i].second;

		int Cnt = (End - Start) / L;

		if ((End - Start) % L != 0)
			Cnt += 1;

		Answer += Cnt;

		PrevEnd = Start + Cnt * L;
	}

	cout << Answer;
}