[백준/BOJ] 백준 2457번 : 공주님의 정원

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

2457번: 공주님의 정원

 

꽃의 날짜 순으로 정렬한 뒤, 해당 순서로 확인하며, 3월 1일부터 11월 30일까지 범위를 앞에서부터 채워 나가며 꽃을 고르는데, 앞에서부터 채우는 꽃을 고를 때, 가능한 꽃이 지는 날짜가 긴 것을 고르도록 그리디 하게 접근하여 문제를 해결했다.

 

코드

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

int n;
int month_day_sum[13];
vector<pair<int, int>> flower;

void pre() {
	for (int i = 1; i <= 12; i++) {
		if (i == 1 || i == 3 || i == 5 || i == 7 || i == 8 || i == 10 || i == 12) {
			month_day_sum[i] = month_day_sum[i - 1] + 31;
		}

		else if (i == 2) {
			month_day_sum[i] = month_day_sum[i - 1] + 28;
		}

		else {
			month_day_sum[i] = month_day_sum[i - 1] + 30;
		}
	}
}

int day_format(int m, int d) {
	return month_day_sum[m - 1] + d;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	pre();

	cin >> n;

	for (int i = 0; i < n; i++) {
		int m1, d1, m2, d2;
		cin >> m1 >> d1 >> m2 >> d2;

		//꽃이 피어 있는 시간 = [day1 ~ day2]
		int day1 = day_format(m1, d1);
		int day2 = day_format(m2, d2) - 1;

		//3월 1일 이전, 11월 30일 이후 날짜는 의미 없으므로 자른다
		day1 = max(day_format(3, 1), day1);
		day2 = min(day_format(11, 30), day2);

		flower.push_back(make_pair(day1, day2));
	}

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

	int result = 0;
	int check_day = day_format(3, 1); //시작점이 check_day 이하 범위를 커버할 수 있는 꽃을 찾는다 
	int check_max_end_day = 0;//시작점이 check_day 이하 범위를 커버할 수 있는 꽃들 중 끝나는 날이 가장 긴 끝나는 날짜
	for (int i = 0; i < flower.size(); i++) {
		int start_day = flower[i].first;
		int end_day = flower[i].second;

		//찾으려는 기준에 충족하는 꽃을 찾았을때
		if (start_day <= check_day && end_day >= check_day) {
			check_max_end_day = max(check_max_end_day, end_day);
		}

		else if (start_day > check_day) { //시작일 기준 자체가 충족하지 않을때
			if (check_max_end_day == 0) { //이전에 구해두었던 꽃이 없을때
				result = 0;
				break;
			}

			//이전에 구해두었던 꽃을 포함한다
			result++;
			check_day = check_max_end_day + 1;
			check_max_end_day = 0;

			if (check_day > day_format(11, 30)) { //조건에 충족하는 꽃을 다 찾았을때
				break;
			}

			i--; //해당 꽃을 다시 확인한다
		}

		if (i == flower.size() - 1) { //모든 꽃을 다 확인 했을때

			if (check_max_end_day == 0) { //이전에 구해두었던 꽃이 없을때
				result = 0;
				break;
			}

			result++;
			check_day = check_max_end_day + 1;
			check_max_end_day = 0;

			if (check_day <= day_format(11, 30)) { //조건에 충족하는 꽃을 다 찾지 못햇을때
				result = 0;
				break;
			}

		}
	}

	cout << result;

	return 0;
}