< 백준 BaekJoon : 2457번 공주님의 정원 > C++

<< 문제 >> 

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

2457번: 공주님의 정원

 

여러 방법으로 풀 수 있을 것 같은데,

저는 뒤에서부터 좁혀오는 방법을 사용했습니다.

 

예시로 보면

4
1 1 5 31
1 1 6 30
5 15 8 31
6 10 12 10

 

11월 30일까지 피어있어야 하니

 

11/30 이후에 지는 꽃을 확인합니다.

그 꽃이 6월 10일에 지니

 

다시, 6월 10일 이후에 지는 꽃들을 확인하는데, 이 때 가장 일찍 피는 꽃을 찾습니다. 

 

이 과정을 반복하면 결과를 도출할 수 있습니다

 

데이터는 월 * 100 + 일로 저장하고 PQ에 넣어 큰 값(늦게 지는 꽃)부터 나오도록 했습니다. 

 

<< 코드 >>

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

int main() {

	int Num;
	cin >> Num;

	priority_queue<vector<int>> TimeTable;
	for (int i = 0; i < Num; i++)
	{
		vector<int> Vec(2); //[끝난 시간, 시작 시간]
		int MonthA, DayA, MonthB, DayB;
		cin >> MonthA >> DayA >> MonthB >> DayB;

		Vec[0] = MonthB * 100 + DayB;
		Vec[1] = MonthA * 100 + DayA;
		TimeTable.push(Vec);
	}
	
	vector<int> NextDay = {1231, 1201};
	int LastDay = 1201;
	int result = 0;

	while (1) {
		// 다음 날짜로 사용할 수 있는 경우, 일단 NextDay에 저장해두고 다음 요소를 확인
		if (TimeTable.top()[0] >= LastDay && NextDay[1] > TimeTable.top()[1]) {
			NextDay = TimeTable.top();
			TimeTable.pop();
		}
		// 지금 저장하고 있는 NextDay보다 더 작은 날짜를 커버하는 경우 지나감
		else if (NextDay[1] <= TimeTable.top()[1]) {
			TimeTable.pop();
		}
		else {
			// LastDay의 최신화
			LastDay = NextDay[1];

			// 연결이 안되는 경우
			if (LastDay > TimeTable.top()[0]) {
				result = 0;
				break;
			}
			result++;
			// 끝나는 경우
			if (LastDay <= 301) { 
				break;
			}
		}
		// 모든 날짜를 다 봤을 때, 3월1일 이하면 result에 1추가
		if (TimeTable.empty()) {
			if (NextDay[1] <= 301 ) {
				result++;
			}
			break;
		}
	}
	

	cout << result << endl;
	
}

 

 

끝

 

<< GitHub >>

https://github.com/J2on/StudyAlgorithm_Part2/tree/main/%EB%B0%B1%EC%A4%80/Gold/2457.%E2%80%85%EA%B3%B5%EC%A3%BC%EB%8B%98%EC%9D%98%E2%80%85%EC%A0%95%EC%9B%90

StudyAlgorithm_Part2/백준/Gold/2457. 공주님의 정원 at main · J2on/StudyAlgorithm_Part2