백준 2457

백준 2457

이 문제는 회의실 배정 문제와 비슷한데, 비교해야할 대상이 4개로 나누어져 있어 비교하기 쉽게 만드는 것이 관건이다. 월과 일을 월에 100을 곱하고 일을 더함으로써 mmdd 형태로 만들면 비교하기가 편하다.

그리고 문제에서 원하는 시작하는 날짜보다 빨리 피거나 늦게 지는 꽃들은 301,1201로 맞춰주었다. 지는 날짜를 기준으로 내림차순으로 정렬을 했다.

12월 1일에 지는 꽃들을 기준으로 가장 빨리 피는 꽃을 먼저 시작점을 잡고, 반복문을 돌면서 가장 적게 겹치는 꽃을 찾아야 하는데 예를 들어
꽃이 6월 15일에 폈다면 6월 15일에 진 꽃을 찾는게 베스트이다.

#include<bits/stdc++.h>
using namespace std;
int n;
vector <pair<int, int >>v;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++) {

		int a, b, c, d;
		cin >> a >> b >> c >> d;

		if ((a == 3 && b == 1) || (a <= 2)) {
			a = 3; b = 1;
		}
		if (c == 12) {
			d = 1;
		}
		v.push_back({ c * 100 + d,a * 100 + b });
	}

	sort(v.begin(), v.end(),greater<>());

	int st = 0, en = 1201; // en 이 1201인 이유 처음 시작점을 잡기 위해서
	int cnt = 0;

	while (en > 301) {

		int nen = 1202;

		for (; st < n; st++) { // 가장 적게 겹치는 꽃을 찾음

			if (en <= v[st].first) {

				if (v[st].first == v[st].second) continue;

				if (nen > v[st].second) {
					nen = v[st].second;
				}
			}
			else break;
		}
		if (nen == 1202) break; // 못찾았으면 탈출
		else {
			cnt++;
			en = nen;
		}
	}
	if (en == 301) cout << cnt;
	else cout << 0;
}

처음에 이중 pair로 잡고 풀다가, 비교하기 힘들어서 구글링을 좀 했다.
합쳐서 생각하면 훨씬 쉬운데... 그걸 못해서 시간이 많이 낭비됐다. 그리고 어떻게 풀지는 감이 잡혔는데, 깔끔하게 코드 구현이 어려움..
효율적으로 푸는 연습을 해야겠다.. ㅠㅠ