[백준/BOJ] 2024. 선분 덮기 [Gold 3]

2024. 선분 덮기

문제출처 : https://www.acmicpc.net/problem/2024

code

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

int main()
{
	vector<pair<int, int>>v(100001);
	int M, index = 0, start = -50001, end = 0, ruler = 0, result = 0;
	cin >> M;
	while (1)
	{
		cin >> v[index].first >> v[index].second;
		if (v[index].first == 0 && v[index].second == 0)
			break;
		index++;
	}
	sort(v.begin(), v.begin() + index);

	for (int i = 0; i < index; i++)
	{
		if (v[i].second < 0)
			continue;
		
		if (v[i].first > start && v[i].first <= end)
		{
			if (ruler <= v[i].second)
				ruler = v[i].second;
			if (v[i].second >= M)
			{
				result++;
				end = M;
				break;
			}
			continue;
		}
		else
			if (end > ruler)
				break;
		result++;
		start = end;
		end = ruler;
	}
	if (end == M)
		cout << result;
	else
		cout << 0;
		

	return 0;
}

이전에 풀었던 공주님 정원꾸미기? 문제랑 완벽히 똑같은 로직이다.
실제로 코드도 거의 비슷하다.