BOJ 2457 공주님의 정원

사용한 알고리즘

그리디 알고리즘

알고리즘 설명

꽃이 피는 달과 일수가 주어지면 이를 일수로 바꿔 저장한다.
꽃이 먼저 피는 순서대로 정렬한다.
시작하는 날짜(3월 1일)보다 먼저 핀 꽃들의 지는 날짜를 힙에 저장한다.
힙에서 가장 늦게 지는 꽃 하나를 뽑고, 이 꽃 전에 피는 꽃을 힙에 저장한다.
위를 반복하고 지는 꽃이 11월 30일 보다 크면 종료한다.
힙에서 가장 늦게 지는 꽃을 확인한 숫자만큼이 필요한 꽃에 개수이다.
중간에 힙에 아무것도 존재하지 않으면 불가능조건으로 0을 출력한다.

풀이

// baekjoon 2457 yechan
#include <cstdio>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
const int MAX_N=100001;
int m[12]={31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int N, s=59, e=333;
pair<int, int> flowers[MAX_N];

int convNum(int month, int day) {
	int ret=0;
	for (int i=0; i<month-1; i++) ret +=m[i];
	return ret+day-1;
}

int no() {
	printf("0\n");
	return 0;
}
int main() {
	scanf("%d", &N);
	for (int i=0; i<N; i++) {
		int m1,d1,m2,d2;
		scanf("%d%d%d%d", &m1, &d1, &m2, &d2);
		flowers[i].first = convNum(m1, d1);
		flowers[i].second = convNum(m2, d2)-1;
	}
	sort(flowers, flowers+N);
	priority_queue<int> q;
	int cur_s=s-1, ret=0;
	int i = 0;
	while (1) {
		while (i < N && flowers[i].first <= cur_s + 1) {
			q.push(flowers[i].second);
			i++;
		}
		if (q.empty() || q.top() <= cur_s) return no();
		cur_s = q.top(); ret++;
		q.pop();
		if (cur_s >= e) break;
	}
	printf("%d\n", ret);
	return 0;
}