BOJ 1911 흙길 보수하기

문제의 힌트를 보면 잘 이해가 되지 않는다. 상식적으로 웅덩이를 덮을때 시작점에 딱 맞춰서 널빤지를 붙이면 최적이다. 

힌트를 보면 웅덩이는 1에서 시작하는데 널빤지를 0에서 부터 붙이기 시작하여 사실상 힌트 오류라고 할수 있다. 

실제 맞는 예시는 다음과 같다.

.111222.333444555

.MMMMM..MMMM.MMMM

 

풀이 방법은 각 웅덩이 위치를 백터 v에 넣어 정렬한 후 각 웅덩이 마다 깔수 있는 널빤지를 구해주면 된다. 

핵심은 널빤지가 다른 웅덩이를 일부 덮는다면 거기서부터 계속 붙여나가고, 그렇지 않고 널빤지의 끝이 일반 땅이라면 그다음 웅덩이부터 다시 붙여나가면 된다.

 

 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, l;
	cin >> n >> l;

	vector<pair<long long, long long>> v;

	
	for(int i = 0; i < n; i++)
	{
		long long s, e;
		cin >> s >> e;
		v.push_back({ s,e });
	}


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

	long long cur = 0;
	int cnt = 0;
	for(int i = 0; i < v.size(); i++)
	{
		if(cur >= v[i].first && cur < v[i].second)
		{
			int quotient = (v[i].second - cur) / l;
			int remainder = (v[i].second - cur) % l;

			cnt += quotient;
			cur += quotient * l;
			if(remainder != 0)
			{
				cnt++;
				cur += l;
			}
		}
		else if(cur< v[i].first)
		{
			cur = v[i].first;
			i--;
		}
	}
	cout << cnt;
}