[G3] 백준 2457번 공주님의 정원 C++ 그리디 알고리즘, 우선순위 큐

리뷰

 

https://www.acmicpc.net/problem/2457

범위가 딱 맞아 떨어지는 부분에 엣지케이스가 상당수 존재하는 것 같다.

 

 

전역 변수

• monts : 각 월에 포함된 일수를 저장할 배열
• pre : 월에 해당하는 일수의 누적합을 저장할 배열
• n : 꽃들의 개수를 저장할 변수
• Date : 꽃이 피는 날짜와 지는 날짜를 정의할 구조체, 피는 날짜 기준으로 오름차순 정렬한다.
• pq : 아직 체크하지 않은 꽃들을 저장할 Date타입 우선순위 큐

 

함수

없음

 

 

문제풀이

1. monts배열을 기준으로 각 일자에 대한 누적합을 pre배열에 초기화한다.
2. 변수 s를 3월 1일의 누적 일자로, e를 12월 1일의 누적일자로 초기화한다.
3. n값을 입력 받고, n개의 꽃의 피는 날짜와 지는 날짜를 입력 받아 pq에 추가한다.
4. pq의 top의 시작 시간이 3월 1일보다 이후인 경우 조기 종료한다.
5. 변수 cur에 pq의 top의 시작시간을 저장하고, ans를 0으로 초기화한다.
6. cur이 e보다 작을 때까지 while루프를 수행한다.
7. pq가 비어있다면 조기종료한다.
8. 변수 mx를 -1로 초기화 하고, pq의 top의 시작 시간이 cur이하인 요소를 모두 꺼내 최대값을 mx에 저장한다.
9. mx가 -1이라면 조기 종료하고, 아니라면 cur에 mx를 저장 후 ans를 증가시킨다.
10. while루프가 종료된 후 ans에 저장된 값을 출력한다.

 

트러블 슈팅

1. 종료 일자를 11월 30일로 설정하여 16%에서 WA를 받았다.
2. 종료 일자를 12월 1일로 수정하여 AC를 받았다.

 

참고 사항

1. 꽃이 지는 날짜엔 꽃이 피어있는 판정이 되지 않는다, 따라서 꽃이 지는날짜가 최소 12월 1일이 되어야 한다.
2. 꽃을 입력 받을때 지는 날짜가 3월 1일 이전이거나 피는 날짜가 12월 1일 이후인 꽃들은 pq에 삽입하지 않았다.
3. 범위를 좀 더 좁히기 위해 시작 일자는 3월 1일 고정, 지는 날짜는 12월 1일로 고정하였다.

 

정답 코드

#include<iostream>
#include<queue>
using namespace std;

int monts[] = { 0, 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
int pre[14];
int n;
struct Date {
	int sd, ed;
	bool operator<(const Date& other) const {
		return sd > other.sd;
	}
};
priority_queue<Date> pq;

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

	for (int i = 2; i < 14; ++i) pre[i] = pre[i - 1] + monts[i];
	int s = pre[3] + 1, e = pre[12] + 1;

	cin >> n;
	for (int i = 0; i < n; ++i) {
		int sm, sd, em, ed; cin >> sm >> sd >> em >> ed;
		int sv = pre[sm] + sd;
		int ev = pre[em] + ed;
		if (ev < s || sv > e) continue;

		sv = max(sv, s);
		ev = min(ev, e);
		pq.push({ sv, ev });
	}

	if (pq.top().sd != s) {
		cout << 0;
		return 0;
	}

	int cur = pq.top().sd;
	int ans = 0;
	while (cur < e) {
		if (pq.empty()) {
			cout << 0;
			return 0;
		}

		int mx = -1;
		while (!pq.empty() && pq.top().sd <= cur) {
			Date date = pq.top(); pq.pop();
			//cout << cur << " " << date.sd << " " << date.ed << "\n";
			if (mx < date.ed) mx = date.ed;
		}

		if (mx == -1) {
			cout << 0;
			return 0;
		}

		cur = mx;
		ans++;
	}
	cout << ans;
}