백준 9878번, Bessie Slows Down 풀이

문제

백준 9878번

풀이

이벤트 T와 D를 순서대로 처리해야 합니다.

이벤트 T와 D 각각에서는 작은 것부터 차례로 봐주면 되지만, T와 D 원소 각각에 대해서는 대소 관계를 정의하기는 어렵습니다.

 

하지만, 매번 T와 D 중에 가장 작은 원소끼리만 비교하여 현재 순간에서 이벤트 T가 먼저 오는지, D가 먼저 오는지 판별하여 처리해주는 것은 쉽습니다.

 

위 작업을 하기 위해서, 현재 시간과 현재 위치를 저장해두며 문제에서 시킨대로 하면 됩니다.

 

작은 것부터 봐주는 과정은 우선순위 큐, 나머지는 구현입니다.

소스코드

#include <bits/stdc++.h>

#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pld> vpld;
typedef unordered_map<int, int> mpii;

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

	int n; cin >> n;
	priority_queue<ld, vld, greater<>> T, D;
	while (n--) {
		char c; ld a;
		cin >> c >> a;
		if (c == 'T') T.push(a);
		else D.push(a);
	}
	ld curr_speed = 1, pos = 0, ans = 0;
	while (!T.empty() || !D.empty()) {
		if (T.empty()) {
			auto d = D.top(); D.pop();
			ans += (d - pos) * curr_speed;
			pos = d;
		} else if (D.empty()) {
			auto t = T.top(); T.pop();
			pos += (t - ans) * (1 / curr_speed);
			ans = t;
		} else {
			auto d = D.top();
			auto t = T.top();
			if (ans + (d - pos) * curr_speed <= t) { //이벤트 D가 앞서는 경우
				ans += (d - pos) * curr_speed;
				pos = d;
				D.pop();
			} else { //이벤트 T가 앞서는 경우
				pos += (t - ans) * (1 / curr_speed);
				ans = t;
				T.pop();
			}
		}
		++curr_speed;
	}

	ans += (1000 - pos) * curr_speed;
	cout << (ll)round(ans);
}