[C++] 백준 2457번 공주님의 정원

그리디로 문제를 해결했습니다.

3월1일부터 11월 30일까지 최소의 갯수를 선택해서 꽃을 피고있게 하는 문제입니다.

3월 1일 아래로 입력받은 것은 3월 1일로 변경해주고
12월 1일 위로 입력받은 것은 전부 12월 1일로 변경해주었습니다.

월일을 표현하기 쉽게하기위해서 월에 100을 곱해주었습니다.
ex) 3월 1일 = 301, 12월 1일 = 1201

1. 시작점은 3월 1일부터 시작해서 최대한 긴것을 골라줍니다.
2. 시작점 부터 고른것의 도착점 사이에 시작하는 것들을 탐색해서 가장 멀리 가는것을 선택해줍니다.
3. 고른것의 시작위치를 시작점으로, 도착위치를 도착점으로 변경해줍니다.
4. 2~3을 반복합니다.
5. 도착점이 원래 도착점보다 작으면 더이상 진행할 수 없는 경우로 0을 출력합니다.
6. 모든 반복을 다 돌았을때 도착점이 1201이 아니면 0을 출력합니다.
7. 그 외의 경우에는 반복한 횟수를 출력해줍니다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
using namespace std;

int main(int argc, char* argv[])
{
	int n;
	int s1, s2, e1, e2;
	int start = 300;
	int end = 301;
	int result = 0;
	int maxEnd = 0;
	int maxIndex = 0;
	vector<pair<int, int> > v;

	cin >> n;

	for (int i = 0; i < n; ++i) {
		cin >> s1 >> s2 >> e1 >> e2;

		if (s1 * 100 + s2 < 301) {
			s1 = 3;
			s2 = 1;
		}

		if (e1 * 100 + e2 > 1130) {
			e1 = 12;
			e2 = 01;
		}

		v.push_back({ s1 * 100 + s2, e1 * 100 + e2 });
	}

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

	for (int i = 0; i < n; ++i) {
		if (v[i].first > start && v[i].first <= end) {
			if (maxEnd < v[i].second) {
				maxEnd = v[i].second;
				maxIndex = i;
			}
			if (v[i].second == 1201) {
				++result;
				end = maxEnd;
				break;
			}
			continue;
		}
		else {
			if (end >= maxEnd) {
				break;
			}

			++result;
			start = end;
			end = maxEnd;
			--i;
		}
	}

	if (end == 1201) {
		cout << result << endl;
	}
	else {
		cout << 0 << endl;
	}

	return 0;
}