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

모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 출력하는 문제이다.

 

문제 해결 방법

1. 물웅덩이 시작 위치를 정렬한다.

2. 널빤지를 놓는다.(저장된 값이 물웅덩이 끝위치보다 크다면 널빤지를 놓지 않는다.)

3. 널빤지가 물웅덩이 끝위치보다 많이 커버한다면 저장한다.

 

#include <iostream>
#include <queue>

using namespace std;

priority_queue<pair<int, int> >Q;

int main(void)
{
	int N=0;
	int L=0;
	
	cin>>N>>L;
	
	for(int i=0; i<N; i++)
	{
		int num1=0;
		int num2=0;
		cin>>num1>>num2;
		
		Q.push(make_pair(-num1,num2));
	}
	
	int count=0;
	int next=0;
	
	while(!Q.empty())
	{
		int num1=-Q.top().first;
		int num2=Q.top().second;
		Q.pop();
		
		if(next>num1)
		{
			num1=next;
		}
		
		if(next<num2)
		{
			int gap=num2-num1;
			int gap2=gap%L;
			
			count=count + gap/L;
			
			if(gap2!=0)
			{
				count++;
				next=num2+(L-gap2);
			}
		}	
	}
	
	cout<<count;
	
	return 0;
}