[백준 1911] 흙길 보수하기

www.acmicpc.net/problem/1911

1911번: 흙길 보수하기

 

이 문제는 priority Queue를 통해 순차적으로 길을 Sorting 한 뒤

하나씩 Pop 하면서 푸는 문제이다.

 

하나의 조건만 생각하면 쉽게 풀리는 문제인데

이전에 다리를 설치해서 보수된 끝영역을 저장하고 

다음으로 흙길이 시작하는 부분과 비교하여 보수된 영역을

고려해주는 방식으로 풀면 된다.

 

#include <iostream>
#include <queue>

using namespace std;

int main(void)
{
	int N = 0;
	int L = 0;
	int M_st = 0;
	int M_fi = 0;
    priority_queue< pair<int, int> > prior_Que;

	int Pos = 0;
	int cnt = 0;

	cin >> N >> L;

	for(int i = 0; i < N; i++)
	{
		cin >> M_st;
		cin >> M_fi;
        pair<int, int> pTmp = make_pair(-M_st, -M_fi);    
        prior_Que.push(pTmp);
	}

    while(!prior_Que.empty())
    {
        pair<int, int> pTmp = prior_Que.top();
        prior_Que.pop();
        
        if(-pTmp.first > Pos) 
            Pos =  -pTmp.first;

        while(-pTmp.second > Pos)
        {
            Pos += L;
            cnt++;
        }
    }

	cout << cnt << endl;

	return 0;
}