2457(그리디)

첫인상

문제를 보자마자 그리디 문제이고 입력값이 십만개여서 nlogn 시간 안에 풀어야 하는 문제임을 인지하고 시작하였다.

풀이

1/1부터 시작해서 목표값을 3/1로 초기화하고 1/1부터 3/1 사이에 피기 시작한 꽃 중에서 가장 늦게 지는 꽃으로 목표값을 수정하며 또 3/1부터 수정된 목표값까지로 범위를 잡고 재귀적으로 찾아주었다. 정렬이 필요했기에 pq를 사용하였다.

문제상황

꽃의 시작 월, 일 끝 월, 일 이렇게 4가지 종류의 데이터를 다루어야 했기에 처음에 struct를 이용해서 접근했는 데 벡터를 사용하여 정렬하거나 우선순위큐를 사용하는 과정에서 어마어마하게 많은 에러가 나서 난항을 겪었다. pair<pair<int,int>, pair<int,int>>를 사용하여 4가지 정보를 한번에 다루었고 이후 우선순위 큐의 사용에도 지장이 없었다.

코드

#include<iostream>
#include<queue>
#include<utility>
#define pii pair<int,int>
#define ppp pair<pii, pii>
using namespace std;

bool cmp(pii endDate, int m, int d) {
	if (endDate.first > m) {
		return true;
	}
	else if (endDate.first == m && endDate.second > d) {
		return true;
	}
	return false;
}



priority_queue<ppp, vector<ppp>, greater<ppp>> date;
int n;

void input() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		ppp ins;
		cin >> ins.first.first >> ins.first.second >> ins.second.first >> ins.second.second;
		date.push(ins);
	}
}

void solve() {
	int targetM = 3;
	int targetD = 1;
	int maxM = 0;
	int maxD = 0;
	int ans = 0;
	bool pop = true;
	pii startDate;
	pii endDate;

	int i = 0;
	while(true){
		if (maxM == 12) {
			cout << ans + 1;
			return;
		}
		
		if (pop) {
			if (date.empty()) {
				break;
			}
			startDate = date.top().first;
			endDate = date.top().second;
			date.pop();
		}
		else {
			pop = true;
		}

		if (startDate.first < targetM || (startDate.first == targetM && startDate.second <= targetD)) {
			if (cmp(endDate, maxM, maxD)) {
				maxM = endDate.first;
				maxD = endDate.second;
			}
		}
		else {
			if (maxM > targetM) {
				targetM = maxM;
				targetD = maxD;
				ans += 1;
				pop = false;
			}
			else if (maxM == targetM && maxD > targetD) {
				targetD = maxD;
				ans += 1;
				pop = false;
			}
			else {
				break;
			}
		}
	}
	cout << 0;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	input();
	solve();
}