[백준] 골드3 : (2457) 공주님의 정원

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

 

처음에 우선순위 큐를 사용해서 시간초과가 나서 안 쓰고 풀었다.

 

문제에서 주의해야 할 점은, 3월 1일에 피고 11월 30일에 지는 꽃은 11월 29일까지만 유효하다는 것이다.

따라서, 문제에서 11월 30일까지 꽃이 피어있어야 하니, 심어야 하는 꽃은 최소 12월 1일 이상에서 져야 한다.

(때문에 End를 1201로 지정)

 

다음으로, 1, 3, 5...월은 31일까지 있고, 나머지는 30일까지 있는 규칙을 굳이 따져야 하나 싶었다.

따라서 그냥 3월1일이면 301로 저장했다. (12월 31일 -> 1231)

이렇게 저장해도 어차피 순서는 같아서 무관하다.

 

로직은 다음과 같다.

11
2 28 8 16
6 18 7 9
9 5 10 25
4 22 8 25
5 22 6 13
8 18 9 16
4 29 10 4
8 23 11 25
6 26 12 1
3 3 10 19
8 3 10 11

먼저 무조건적으로 들어가는 꽃을 찾아야 한다.

 

12월 1일을 넘어서 지는 꽃은 [ 6 26 12 1 ] 꽃 하나밖에 없기 때문에, 무조건 이 꽃은 들어가야 한다.

이 꽃을 선택하면, 다음 타깃으로는 이전 꽃의 피는 날을 넘어서 지는 꽃을 찾아야 한다.

 

해당 입력에서 6월 26일보다 넘어 지는 꽃은 9개가 있다.

이 중에서, 가장 꽃이 피는 날이 낮은(1월 1일에 가까운) 꽃으로 선택한다.

 

결론적으로, [ 2 28 8 16 ] 꽃과 [ 6 26 12 1 ] 꽃 2개가 필요하다.

 

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

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

	int N, Answer = 0, Start = 301, End = 1201; // 시작과 끝을 선언한다. (꽃이 피어있어야 하는 구간)
	cin >> N;

	// 꽃들의 피는 날과 지는 날을 저장할 큐
	queue<pair<int, int>> q;
	for (int i = 0; i < N; ++i)
	{
		string m1, d1, m2, d2;
		cin >> m1 >> d1 >> m2 >> d2;

		// ex. 3월 1일이면, 301로 저장한다.
		if (d1.size() == 1) d1 = "0" + d1;
		if (d2.size() == 1) d2 = "0" + d2;

		q.push({ stoi(m1 + d1), stoi(m2 + d2) });
	}

	while (Start < End) // 꽃이 피어있는 구간이 더 많으면 종료 (이분 탐색이랑 비슷?)
	{
		int size = q.size(), Min = 100001;

		for (int i = 0; i < size; ++i)
		{
			pair<int, int> a = q.front();
			q.pop();

			if (a.second >= End) Min = min(Min, a.first); // 이전 꽃의 피는 날을 넘어서 지는 꽃 중에서 가장 피는 날이 낮은 꽃
			else if (a.first < End) q.push(a); // 꽃의 피는 날이 현재 꽃의 지는 날보다 나중이면 버림
		}

		if (Min == 100001) { cout << 0 << "\n"; return 0; }
		End = Min, Answer++;
	}

	cout << Answer << "\n";
}